Minimum degree conditions for monochromatic cycle partitioning
A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2logr) monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any r-edge-coloure...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2021
|
| In: |
Journal of combinatorial theory
Year: 2020, Jahrgang: 146, Pages: 96-123 |
| DOI: | 10.1016/j.jctb.2020.07.005 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jctb.2020.07.005 Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S0095895620300721 
|
| Verfasserangaben: | Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy |
| Zusammenfassung: | A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2logr) monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any r-edge-coloured graph on n vertices with minimum degree at least n/2+c⋅rlogn has a partition into O(r2) monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight. |
|---|---|
| Beschreibung: | Available online 27 August 2020 Gesehen am 08.02.2021 |
| Beschreibung: | Online Resource |
| DOI: | 10.1016/j.jctb.2020.07.005 |