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

Abstract

We extend the conjecture of Erdős and Gyárfás 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, that together cover all vertices. The order of the bound is best possible, and the ceiling is necessary for infinitely many $n$.

16 pages