Monochromatic cycle partitions in random graphs

Richard Lang; Allan Lo

doi:10.1017/S0963548320000401

Monochromatic cycle partitions in random graphs

Richard Lang, Allan Lo

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

219 Downloads (Pure)

Abstract

Erdős, Gyárfás and Pyber showed that every r-edge-coloured complete graph K_n can be covered by 25r²logr 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 1000r⁴logr 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	https://doi.org/10.1017/S0963548320000401
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

Access to Document

10.1017/S0963548320000401Licence: Creative Commons: Attribution (CC BY)

LangR2020Monochromatic Final published version, 429 KBLicence: Creative Commons: Attribution (CC BY)

https://doi.org/10.1017/S0963548320000401Licence: Creative Commons: Attribution (CC BY)

A graph theoretical approach for combinatorial designs
Lo, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils

Cite this

@article{07437416f90d4606b755d6adeb33a260,

title = "Monochromatic cycle partitions in random graphs",

abstract = "Erd{\H o}s, Gy{\'a}rf{\'a}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{\'a}ndi, Mousset, Nenadov, {\v S}kori{\'c} and Sudakov",

author = "Richard Lang and Allan Lo",

year = "2020",

month = aug,

day = "14",

doi = "10.1017/S0963548320000401",

language = "English",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Monochromatic cycle partitions in random graphs

AU - Lang, Richard

AU - Lo, Allan

PY - 2020/8/14

Y1 - 2020/8/14

N2 - 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

AB - 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

UR - http://www.scopus.com/inward/record.url?scp=85094980997&partnerID=8YFLogxK

U2 - 10.1017/S0963548320000401

DO - 10.1017/S0963548320000401

M3 - Article

SN - 0963-5483

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

Monochromatic cycle partitions in random graphs

Abstract

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

A graph theoretical approach for combinatorial designs

Cite this