Monochromatic cycle partitions in random graphs

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

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

Details

Original languageEnglish
Number of pages16
JournalCombinatorics, Probability and Computing
Publication statusAccepted/In press - 8 Apr 2020