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 $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $\vec{T}_4$'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $\vec{T}_k$'s., 18 pages, 3 figures. Minor updates based on referee reports

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

Corradi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all $$k\ge 1$$ and $$n\ge 3k$$ , every (simple) graph G on n vertices with minimum degree $$\delta (G)\ge 2k$$ contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corradi–Hajnal theorem: For all $$k\ge 1$$ and $$n\ge 3k$$ , every graph G on n vertices contains k disjoint cycles, provided that $$d(x)+d(y)\ge 4k-1$$ for all distinct nonadjacent vertices x, y. Very recently, it was refined for $$k\ge 3$$ and $$n\ge 3k+1$$ : If G is a graph on n vertices such that $$d(x)+d(y)\ge 4k-3$$ for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number $$\alpha (G)\le n-2k$$ and G is not one of two small exceptions in the case $$k=3$$ . But the most difficult case, $$n=3k$$ , was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corradi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.

The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with (G) = o(n) and (G) (1=2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)

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.

Corradi and Hajnal in 1963 proved the following theorem on the NP-complete problem on the existence of k disjoint cycles in an n-vertex graph G: For all k ≥ 1 and n ≥ 3k, every (simple) n-vertex graph G with minimum degree δ(G) ≥ 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k − 1)-connected multigraphs do not contain k disjoint cycles? Recently, Kierstead, Kostochka, and Yeager resolved this question. In this paper, we sharpen this result by presenting a description that can be checked in polynomial time of all multigraphs G with no k disjoint cycles for which the underlying simple graph \( \underline {G}\) satisfies the following Ore-type condition: \(d_{ \underline {G}}(v)+d_{ \underline {G}}(u)\geq 4k-3\) for all nonadjacent u, v ∈ V (G).

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.

Hajnal and Szemerédi proved that every graph G with |G| = ks and δ(G)⩾ k(s − 1) contains k disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph $\vv G$ with |$\vv G$| = ks and δ($\vv G$) ⩾ 2k(s − 1) − 1 contains k disjoint transitive tournaments on s vertices, where δ($\vv G$)= minv∈V($\vv G$)d−(v)+d+(v). Our result implies the Hajnal–Szemerédi theorem, and its degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.

In 2006, Kuhn and Osthus [J. Combin. Theory Ser. B, 96 (2006), pp. 767--821] showed that if a 3-graph $H$ on $n$ vertices has minimum codegree at least $(1/4 +o(1))n$ and $n$ is even, then $H$ has a loose Hamilton cycle. In this paper, we prove that the minimum codegree of $n/4$ suffices. The result is tight.

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 this note we introduce the concept of equitable d-relaxed coloring. We prove that each graph with maximum degree at most r admits an equitable 1-relaxed r-coloring and provide a polynomial-time algorithm for constructing such a coloring.

We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an $n$-vertex graph $G$ with sublinear independence number. In this setting, we show that if $\delta(G) \ge n/3 + o(n)$ then $G$ has a triangle-tiling covering all but at most four vertices. Also, for every $r \ge 5$, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that $G$ is $K_r$-free and $n$ is divisible by $3$., Comment: 24 pages

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.

Let $n$ be sufficiently large and suppose that $G$ is a digraph on $n$ vertices where every vertex has in- and outdegree at least $n/2$. We show that $G$ contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is $n/2+1$. Our result is best possible and improves on an approximate result by H\"aggkvist and Thomason., Comment: Final version, to appear in SIAM Journal Discrete Mathematics (SIDMA)