Abstract

Lehel conjectured in the 1970s that the vertices of every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomass & eacute;. However, the host graph G does not have to be complete. It suffices to require that G has minimum degree at least 3n/4, n / 4, where n is the order of G , as was shown recently by Letzter, confirming a conjecture of Balogh, Bar & aacute;t, Gerbner, Gy & aacute;rf & aacute;s and S & aacute;rk & ouml;zy. This degree condition is 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 n / 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. (c) 2023 Elsevier Ltd. All rights reserved.