Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree

Abstract

A question posed independently by Letzter and Pokrovskiy asks: how many vertex-disjoint monochromatic cycles are needed to cover the vertex set of an $r$-edge-coloured graph, as a function of its minimum (uncoloured) degree? We resolve this problem up to a $(\log r)$-factor. Specifically, we prove that, for any $r\ge 2$ and $\delta \in (0,1/2)$, any $n$-vertex $r$-edge-coloured graph $G$ with $\delta (G)\ge (1-\delta )n$ can be covered with $\mathcal{O}(r\log r\cdot \lceil r/\log (1/\delta )\rceil )$ vertex-disjoint monochromatic cycles. We construct graphs that show this is tight up to the $(\log r)$-factor for all values of $r$ and $\delta$, and along the way disprove a conjecture of Bal and DeBiasio about monochromatic tree covering.

44 pages