Monochromatic cycle partitions in random graphs

Research output: Contribution to journalArticlepeer-review

Colleges, School and Institutes


Erdős, Gyárfás and Pyber showed that every r-edge-coloured complete graph Kn can be covered by 25r2logr 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)≥Ω(n−1/(2r)), then with high probability any r-edge-coloured G(n,p) can be covered by at most 1000r4logr vertex-disjoint monochromatic cycles. This answers a question of Korándi, Mousset, Nenadov, Škorić and Sudakov


Original languageEnglish
JournalCombinatorics, Probability and Computing
Early online date14 Aug 2020
Publication statusE-pub ahead of print - 14 Aug 2020