Rainbow Lehel conjecture

For every integer $n\ge 1$ and every proper edge-colouring $c:E(K_n)\to\mathcal{C},$ there exist vertex-disjoint rainbow cycles $C_1,C_2$ such that $V(C_1)\mathbin{\dot\cup}V(C_2)=V(K_n).$ Here, proper means that adjacent edges receive distinct colours, and rainbow means that all edges of each cycle receive pairwise distinct colours.

Progress summary

Partially solved

A new preprint proves the rainbow statement for all sufficiently large complete graphs, but the exact threshold and smaller cases remain open.

The Rainbow Lehel conjecture asks for a rainbow analogue of the classical cycle-partition phenomenon in properly coloured complete graphs. No proposer or original date was identified in the retrieved sources.

August 2026 preprint

Peter Keevash and Benny Sudakov report a proof of the rainbow counterpart for sufficiently large $n$ . The result establishes asymptotic progress, but the threshold is not claimed to be exact.

Current status (as of August 2026): The sufficiently-large- $n$ case is established in the Keevash–Sudakov preprint, while the exact threshold and smaller cases remain open.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

A rainbow version of Lehel's conjecture — arXiv — Peter Keevash, Benny Sudakov

extremal-combinatorics graph-theory

2 days ago