Monochromatic cycle partitions in random graphs
Erdős, Gyárfás and Pyber showed that every r-edge-coloured complete graph Kn can be covered by 25 r2 log r 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 - - - - - , then with high probab...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2021
|
| In: |
Combinatorics, probability & computing
Year: 2021, Volume: 30, Issue: 1, Pages: 136-152 |
| ISSN: | 1469-2163 |
| DOI: | 10.1017/S0963548320000401 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/S0963548320000401 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/monochromatic-cycle-partitions-in-random-graphs/880B178D98CC67FB4D353847851CF3A6 
|
| Author Notes: | Richard Lang and Allan Lo |
| Summary: | Erdős, Gyárfás and Pyber showed that every r-edge-coloured complete graph Kn can be covered by 25 r2 log r 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 - - - - - , then with high probability any r-edge-coloured G(n, p) can be covered by at most 1000r4 log r vertex-disjoint monochromatic cycles. This answers a question of Korándi, Mousset, Nenadov, Škorić and Sudakov. |
|---|---|
| Item Description: | First published online 14 August 2020 Gesehen am 09.09.2021 |
| Physical Description: | Online Resource |
| ISSN: | 1469-2163 |
| DOI: | 10.1017/S0963548320000401 |