Minimum degree conditions for monochromatic cycle partitioning

• Verfasst von: Korándi, Dániel [VerfasserIn]
• Verfasst von: Lang, Richard [VerfasserIn]
• Verfasst von: Letzter, Shoham [VerfasserIn]
• Verfasst von: Pokrovskiy, Alexey [VerfasserIn]
• Titel: Minimum degree conditions for monochromatic cycle partitioning
• Verf.angabe: Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy
• Jahr: 2021
• Jahr des Originals: 2020
• Umfang: 28 S.
• Fussnoten: Available online 27 August 2020 ; Gesehen am 08.02.2021
• Titel Quelle: Enthalten in: Journal of combinatorial theory / B
• Ort Quelle: Orlando, Fla. : Academic Press, 1971
• Jahr Quelle: 2021
• Band/Heft Quelle: 146(2021), Seite 96-123
• DOI: doi:10.1016/j.jctb.2020.07.005
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Dirac-type problems
• Sach-SW: Hamilton cycles
• Sach-SW: Monochromatic cycle partitioning
• Sach-SW: Ramsey theory
• K10plus-PPN: 1747731072

Abstract

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.