Monochromatic cycle partitions in random graphs

Richard Lang, Allan Lo

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
167 Downloads (Pure)

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
Original languageEnglish
JournalCombinatorics, Probability and Computing
Early online date14 Aug 2020
DOIs
Publication statusE-pub ahead of print - 14 Aug 2020

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Monochromatic cycle partitions in random graphs'. Together they form a unique fingerprint.

Cite this