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...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2021
|
| In: |
Combinatorics, probability & computing
Year: 2021, Jahrgang: 30, Heft: 1, Pages: 136-152 |
| ISSN: | 1469-2163 |
| DOI: | 10.1017/S0963548320000401 |
| Online-Zugang: | 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 
|
| Verfasserangaben: | Richard Lang and Allan Lo |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1753145406 | ||
| 003 | DE-627 | ||
| 005 | 20220819154044.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 210406s2021 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1017/S0963548320000401 |2 doi | |
| 035 | |a (DE-627)1753145406 | ||
| 035 | |a (DE-599)KXP1753145406 | ||
| 035 | |a (OCoLC)1341403329 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Lang, Richard |e VerfasserIn |0 (DE-588)122670008X |0 (DE-627)1747737372 |4 aut | |
| 245 | 1 | 0 | |a Monochromatic cycle partitions in random graphs |c Richard Lang and Allan Lo |
| 264 | 1 | |c 2021 | |
| 300 | |a 17 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a First published online 14 August 2020 | ||
| 500 | |a Gesehen am 09.09.2021 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 05C38 | |
| 650 | 4 | |a 05D10 | |
| 700 | 1 | |a Lo, Allan |d 1983- |e VerfasserIn |0 (DE-588)1189854465 |0 (DE-627)1668609223 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Combinatorics, probability & computing |d Cambridge : Cambridge Univ. Press, 1992 |g 30(2021), 1, Seite 136-152 |h Online-Ressource |w (DE-627)271601256 |w (DE-600)1481145-5 |w (DE-576)07870927X |x 1469-2163 |7 nnas |a Monochromatic cycle partitions in random graphs |
| 773 | 1 | 8 | |g volume:30 |g year:2021 |g number:1 |g pages:136-152 |g extent:17 |a Monochromatic cycle partitions in random graphs |
| 856 | 4 | 0 | |u https://doi.org/10.1017/S0963548320000401 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/monochromatic-cycle-partitions-in-random-graphs/880B178D98CC67FB4D353847851CF3A6 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20210406 | ||
| 993 | |a Article | ||
| 994 | |a 2021 | ||
| 998 | |g 122670008X |a Lang, Richard |m 122670008X:Lang, Richard |d 110000 |d 110300 |e 110000PL122670008X |e 110300PL122670008X |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1753145406 |e 3902089873 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"note":["First published online 14 August 2020","Gesehen am 09.09.2021"],"type":{"bibl":"article-journal","media":"Online-Ressource"},"recId":"1753145406","language":["eng"],"person":[{"family":"Lang","given":"Richard","roleDisplay":"VerfasserIn","display":"Lang, Richard","role":"aut"},{"role":"aut","display":"Lo, Allan","roleDisplay":"VerfasserIn","given":"Allan","family":"Lo"}],"title":[{"title":"Monochromatic cycle partitions in random graphs","title_sort":"Monochromatic cycle partitions in random graphs"}],"physDesc":[{"extent":"17 S."}],"relHost":[{"title":[{"title_sort":"Combinatorics, probability & computing","title":"Combinatorics, probability & computing","subtitle":"CPC"}],"titleAlt":[{"title":"CPC"}],"part":{"volume":"30","text":"30(2021), 1, Seite 136-152","extent":"17","year":"2021","pages":"136-152","issue":"1"},"pubHistory":["1.1992 -"],"language":["eng"],"recId":"271601256","type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"Monochromatic cycle partitions in random graphsCombinatorics, probability & computing","note":["Gesehen am 05.03.2018"],"id":{"issn":["1469-2163"],"eki":["271601256"],"zdb":["1481145-5"]},"origin":[{"dateIssuedDisp":"1992-","dateIssuedKey":"1992","publisher":"Cambridge Univ. Press","publisherPlace":"Cambridge"}],"physDesc":[{"extent":"Online-Ressource"}]}],"name":{"displayForm":["Richard Lang and Allan Lo"]},"origin":[{"dateIssuedDisp":"2021","dateIssuedKey":"2021"}],"id":{"doi":["10.1017/S0963548320000401"],"eki":["1753145406"]}} | ||
| SRT | |a LANGRICHARMONOCHROMA2021 | ||