Cover Image

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(r2log⁡r) 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...

Full description

Saved in:
Bibliographic Details
Main Authors: Korándi, Dániel (Author) , Lang, Richard (Author) , Letzter, Shoham (Author) , Pokrovskiy, Alexey (Author)
Format: Article (Journal)
Language:English
Published: 2021
In: Journal of combinatorial theory
Year: 2020, Volume: 146, Pages: 96-123
DOI:10.1016/j.jctb.2020.07.005
Online Access:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jctb.2020.07.005
Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S0095895620300721
Get full text
Author Notes:Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy
Description
Summary:A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2log⁡r) 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⋅rlog⁡n 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.
Item Description:Available online 27 August 2020
Gesehen am 08.02.2021
Physical Description:Online Resource
DOI:10.1016/j.jctb.2020.07.005

Similar Items