Preprint

A rainbow version of Lehel's conjecture

Pedro Araújo Xiao-Chuan Liu Taísa L. Martins Walner Mendonça Luiz Moreira V. D. dos Santos Zhi-Fei Yan

Aug 2026 · 0 citations · 12 references

Mathematics

Abstract

Lehel's conjecture states that every 2-edge-colouring of K_n admits a partition of its vertex set into two monochromatic cycles. It was proven for sufficiently large n by {\L}uczak, R\"odl, and Szemer\'edi in 1998, later improved by Allen in 2008, and fully resolved by Bessy and Thomass\'e in 2010. In this paper, we consider a rainbow analogue of Lehel's conjecture in the setting of properly edge-coloured complete graphs. We prove that, for sufficiently large n, every properly edge-coloured Kn admits a partition of its vertex set into two vertex-disjoint rainbow cycles

arXiv Semantic Scholar

View source

Similar papers

Preprint Sep 2026

A Proof of Albertson's Conjecture

Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of orde...

A. Sadhu · 1 citation

Preprint Aug 2026

An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision

Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $\Omega(k^{8/11})$ bound for this conjecture, improving upon the $\Omega(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement...

Douglas M. Chen · 1 citation · ⚡1

Preprint Aug 2026

A relaxation of the Bermond-Thomassen conjecture

The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint directed cycles. Despite being posed in 1981, this conjecture remains unresolved for all $k \ge 4$. We prove a relaxation of this conjecture: every digraph $D$ of minimum out-degree a...

S. Bessy, M. Muis, Jean-Sébastien Sereni et al. · 1 citation

Preprint Sep 2026

A Counterexample to Wormald's Conjecture

We give a counterexample to Wormald's conjecture. A 16-vertex cubic graph, the disjoint union of $K_{3,3}$ with a 10-vertex bridged graph built from two subdivided copies of $K_4$, has no partition of its edges into two isomorphic spanning linear forests. The obstruction is parity: any such partition would force every...

James Alexander Schreib · 0 citations

Preprint Aug 2026

Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs

We extend the conjecture of Erd\H{o}s and Gy\'arf\'as on monochromatic path covers to the setting of monochromatic cycle covers. We prove that, for all $n$, every 2-edge-coloring of the complete graph on $n$ vertices contains a collection of at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, th...

Xiao-Chuan Liu, Jonatas Teodomiro, Xu Yang · 0 citations

Preprint Sep 2026

A nearly linear bound for the Lov\'asz conjecture

The celebrated conjecture of Lov\'asz from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Buci\'c, Christoph, Pokrovskiy and Steiner recently proved that every such graph on $n$ vertices contains a cycle of length $n^{2/3-o(1)}$. In this paper, we improve this bound to $n^{1-o(1)}$. O...

Bo-Wen Li, Abhishek Methuku · 2 citations