Monochromatic cycle partitions in random graphs

Abstract

Erdős, Gyárfás and Pyber showed that every $r$-edge-coloured complete graph $K_n$ can be covered by $25r^2\log r$ vertex-disjoint monochromatic cycles (independent of $n$). Here, we extend their result to the setting of binomial random graphs. That is, we show that if $p=p(n)=\Omega (n^{-1/(2r)})$, then with high probability any $r$-edge-coloured $G(n,p)$ can be covered by at most $1000r^4\log r$ vertex-disjoint monochromatic cycles. This answers a question of Korándi, Mousset, Nenadov, Škorić and Sudakov.

16 pages, accepted in Combinatorics, Probability and Computing