Minimum degree conditions for monochromatic cycle partitioning - Korándi, Dániel; Lang, Richard; Letzter, Shoham; Pokrovskiy, Alexey (Journal of combinatorial theory, 2021)
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.
Available online 27 August 2020
Gesehen am 08.02.2021