Projects per year
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 language | English |
---|---|
Journal | Combinatorics, Probability and Computing |
Early online date | 14 Aug 2020 |
DOIs | |
Publication status | E-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.Projects
- 1 Finished
-
A graph theoretical approach for combinatorial designs
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils