Partitioning a 2-edge-coloured graph of minimum degree $2n/3+o(n)$ into three monochromatic cycles

Abstract

Lehel conjectured in the 1970s that every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomassé. However, the host graph $G$ does not have to be complete. It it suffices to require that $G$ has minimum degree at least $3n/4$, where $n$ is the order of $G$, as was shown recently by Letzter, confirming a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy. This degree condition is asymptotically tight. Here we continue this line of research, by proving that for every red and blue edge-colouring of an $n$-vertex graph of minimum degree at least $2n/3+o(n)$, there is a partition of the vertex set into three monochromatic cycles. This approximately verifies a conjecture of Pokrovskiy and is essentially tight.

References in corpus (4)

• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Vertex covers by monochromatic pieces - A survey of results and problems
• Monochromatic cycle partitions in random graphs
• Partitioning a graph into a cycle and a sparse graph