Projects per year
Abstract
Erdős, Gyárfás and Pyber showed that every redgecoloured complete graph K_{n} can be covered by 25r^{2}logr vertexdisjoint 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 redgecoloured G(n,p) can be covered by at most 1000r^{4}logr vertexdisjoint 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  Epub 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