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.

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.

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

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.