Zhifei Yan, A Rainbow version of Lehel’s conjecture

Lehel’s conjecture states that every 2-edge-colouring of the complete graph $K_n$ admits a partition of its vertices into two monochromatic cycles. This was proven for sufficiently large n by Luczak, Rödl, and Szemerédi (1998), extended by Allen (2008), and fully resolved by Bessy and Thomassé in 2010.

We consider a rainbow version of Lehel’s conjecture for properly edge-coloured complete graphs. We prove that for any properly edge-coloured $K_n$ with sufficiently large n, there exists a partition of the vertex set into two rainbow cycles, each containing no two edges of the same colour.

This is joint work with Pedro Araújo, Xiaochuan Liu, Taísa Martins, Walner Mendonça, Luiz Moreira, and Vinicius Fernandes dos Santos.