Search

We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph $G$ on $n$ vertices has a rainbow cycle on at least $n - O(n^{3/4})$ vertices, by showing that $G$ has a rainbow cycle on at least $n - O(\log n \sqrt{n})$ vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamilton cycle in which at least $n - O((\log n)^2)$ different colors appear. For large $n$, this is an improvement of the previous best known lower bound of $n - \sqrt{2n}$ of Andersen., Comment: 12 pages

The leaf distance of a tree is the maximum d such that the distance between any pair of leaves in the tree is at least d. Kaneko provided sufficient conditions to force the existence of a spanning tree with leaf distance at least d=3 and conjectured that similar conditions suffice for larger d. The case when d=4 was later proved by Kaneko, Kano, and Suzuki. In this paper, we show that when d4, a stronger form of this conjecture holds for graphs with independence number at most five. As an immediate corollary, we obtain that when dn3, this stronger version holds for all n-vertex graphs, consequently proving Kanekos conjecture for dn3.

In this paper, we prove an analogue of Corradi and Hajnal's classical theorem. There exists n0n0 such that for every n∈3Zn∈3Z when n≥n0n≥n0 the following holds. If G is an oriented graph on n vertices and every vertex has both indegree and outdegree at least 7n/187n/18, then G contains a perfect transitive triangle tiling, which is a collection of vertex-disjoint transitive triangles covering every vertex of G . This result is best possible, as, for every n∈3Zn∈3Z, there exists an oriented graph G on n vertices without a perfect transitive triangle tiling in which every vertex has both indegree and outdegree at least ⌈7n/18⌉−1⌈7n/18⌉−1.

Both Cuckler and Yuster independently conjectured that when $n$ is an odd positive multiple of $3$ every regular tournament on $n$ vertices contains a collection of $n/3$ vertex-disjoint copies of the cyclic triangle. Soon after, Keevash and Sudakov proved that if $G$ is an orientation of a graph on $n$ vertices in which every vertex has both indegree and outdegree at least $(1/2 - o(1))n$, then there exists a collection of vertex-disjoint cyclic triangles that covers all but at most $3$ vertices. In this paper, we resolve the conjecture of Cuckler and Yuster for sufficiently large $n$., Comment: 17 pages

Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v \in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $\ell$-cycle $C_{\ell}$ whenever $n \ge 432 \ell$. This result is sharp for all odd integers $\ell \geq 3$, and extends earlier work of the authors for when $\ell$ is even., 10 pages

In 1963, Corradi and Hajnal settled a conjecture of Erdős by showing that every graph on at least 3 r vertices with minimum degree at least 2 r contains a collection of r disjoint cycles, and in 2008, Finkel proved that every graph with at least 4 s vertices and minimum degree at least 3 s contains a collection of s disjoint chorded cycles. The same year, a generalization of this theorem was conjectured by Bialostocki, Finkel, and Gyarfas: every graph with at least 3 r + 4 s vertices and minimum degree at least 2 r + 3 s contains a collection of r + s disjoint cycles, s of them chorded. This conjecture was settled and further strengthened by Chiba et al. (2010). In this paper, we characterize all graphs on at least 3 r + 4 s vertices with minimum degree at least 2 r + 3 s − 1 that do not contain a collection of r + s disjoint cycles, s of them chorded. In addition, we provide a conjecture regarding the minimum degree threshold for the existence of r + s disjoint cycles, s of them chorded, and we prove an approximate version of this conjecture.

The Hajnal–Szemerédi theorem states that for any positive integer $r$ and any multiple $n$ of $r$, if $G$ is a graph on $n$ vertices and $\unicode[STIX]{x1D6FF}(G)\geqslant (1-1/r)n$, then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any positive integer $r$ with $r\neq 3$ and any sufficiently large multiple $n$ of $r$, if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1-1/r)n-1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices (the case $r=3$ is different and was handled previously). In fact, this result is a consequence of a tiling result for standard multigraphs (that is multigraphs where there are at most two edges between any pair of vertices). A related Turán-type result is also proven.

For k ∈ N , Corradi and Hajnal proved that every graph G on 3 k vertices with minimum degree δ ( G ) ≥ 2 k has a C 3 -factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle C 3 . Wang proved that every directed graph G on 3 k vertices with minimum total degree δ t ( G ) ≔ min v ∈ V ( d e g − ( v ) + d e g + ( v ) ) ≥ 3 ( 3 k − 1 ) / 2 has a C 3 -factor, where C 3 is the directed 3-cycle. The degree bound in Wang’s result is tight. However, our main result implies that for all integers a ≥ 1 and b ≥ 0 with a + b = k , every directed graph G on 3 k vertices with minimum total degree δ t ( G ) ≥ 4 k − 1 has a factor consisting of a copies of T 3 and b copies of C 3 , where T 3 is the transitive tournament on three vertices. In particular, using b = 0 , there is a T 3 -factor of G , and using a = 1 , it is possible to obtain a C 3 -factor of G by reversing just one edge of G . All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph G on 3 k vertices with minimum semidegree δ 0 ( G ) ≔ min v ∈ V min ( d e g − ( v ) , d e g + ( v ) ) ≥ 2 k has a C 3 -factor, and prove that this is asymptotically correct.

In 1960, Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if D is a directed graph on n vertices with minimum out-degree and in-degree at least n/2 (i.e. minimum semi-degree at least n/2), then D contains a directed Hamiltonian cycle. Of course there are other orientations of a cycle in a directed graph and it is not clear that the semi-degree threshold for the directed Hamiltonian cycle is the same as the semi-degree threshold for some other orientation. In 1980, Grant initiated the problem of determining the minimum semi-degree threshold for the anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even n, if D is a directed graph on n vertices with minimum semi-degree at least n/2+1, then D contains an anti-directed Hamiltonian cycle. This result is sharp., 20 pages, 3 figures

An edge-ordering of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an increasing path if it is a path in $G$ which satisfies $\phi(e_i)

In 1963, Corradi and Hajnal settled a conjecture of Erd?s by proving that, for all $$k \ge 1$$k?1, any graph G with $$|G| \ge 3k$$|G|?3k and minimum degree at least 2k contains k vertex-disjoint cycles. In 2008, Finkel proved that for all $$k \ge 1$$k?1, any graph G with $$|G| \ge 4k$$|G|?4k and minimum degree at least 3k contains k vertex-disjoint chorded cycles. Finkel's result was strengthened by Chiba, Fujita, Gao, and Li in 2010, who showed, among other results, that for all $$k \ge 1$$k?1, any graph G with $$|G| \ge 4k$$|G|?4k and minimum Ore-degree at least $$6k-1$$6k-1 contains k vertex-disjoint chorded cycles. We refine this result, characterizing the graphs G with $$|G| \ge 4k$$|G|?4k and minimum Ore-degree at least $$6k-2$$6k-2 that do not have k vertex-disjoint chorded cycles.