UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Minimum degree conditions for monochromatic cycle partitioning

Korándi, D; Lang, R; Letzter, S; Pokrovskiy, A; (2021) Minimum degree conditions for monochromatic cycle partitioning. Journal of Combinatorial Theory, Series B , 146 pp. 96-123. 10.1016/j.jctb.2020.07.005. (In press).

[img] Text
r-colours-final.pdf - Accepted version
Access restricted to UCL open access staff until 28 August 2021.

Download (418kB)

Abstract

A classical result of Erd˝os, Gy´arf´as and Pyber states that any r-edge-coloured complete graph has a partition into O(r 2 log 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 · r log n has a partition into O(r 2 ) monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight.

Type: Article
Title: Minimum degree conditions for monochromatic cycle partitioning
DOI: 10.1016/j.jctb.2020.07.005
Publisher version: https://doi.org/10.1016/j.jctb.2020.07.005
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Monochromatic cycle partitioning, Ramsey theory, Hamilton cycles, Dirac-type problems
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107291
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item