Minimum degree conditions for monochromatic cycle partitioning

Abstract

A classical result of Erdős, Gyárfás and Pyber states that any $r$-edge-coloured complete graph has a partition into $O(r^2\log r)$ monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant $c$ such that any $r$-edge-coloured graph on $n$ vertices with minimum degree at least $n/2+c\cdot r\log n$ has a partition into $O(r^2)$ monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight.

22 pages (26 including appendix)