Erdős–Gyárfás monochromatic cycle-cover conjecture

The conjecture asks how many vertex-disjoint monochromatic cycles are sufficient to cover every edge-coloured complete graph. The two-colour case is settled, while the general problem has resisted the conjectured linear bound.

Known results

• Erdős, Gyárfás, and Pyber obtained $f(r) \le 25r^{2}\log r$ and conjectured $f(r)=r$.
• Bessy and Thomassé proved the $r=2$ case for all $n$.
• Pokrovskiy (2012) disproved $f(r)=r$ for every $r\ge 3$.
• A 2026 preprint gives a lower bound $(1-o(1))r\log\log r$, suggesting an $\Theta(r\log r)$ scale rather than a linear one.

August 2026 sharp square-root extension

A newly listed preprint, “Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs,” claims to extend the path-cover phenomenon to cycle covers with a sharp square-root bound, determining the correct asymptotic order and showing that the exact ceiling cannot generally be removed. The proof is not yet peer reviewed.

Current status (as of August 2026): The two-colour case is settled and the general linear conjecture is false for $r\ge 3$; a sharp asymptotic cycle-cover extension is claimed, but remains unverified.