Two Rainbow Cycles Extend Lehel’s Partition Theorem

Lehel’s conjecture asks whether the vertices of a complete graph whose edges have two colours can always be split between two monochromatic cycles. That question is settled, but its rainbow counterpart changes the constraint: instead of assigning one colour to each cycle, every edge within each cycle must have a distinct colour. The paper proves that this stronger local diversity requirement is still compatible with a two-cycle partition when the host graph is a sufficiently large properly edge-coloured complete graph.

Core Contribution

The central result is a rainbow analogue of Lehel’s conjecture. For sufficiently large $n$, every proper edge-colouring of $K_n$ admits two vertex-disjoint rainbow cycles whose vertex sets partition $V(K_n)$. In other words, every vertex belongs to exactly one of the two cycles, and neither cycle repeats an edge colour.

The distinction from the classical statement is substantial. A two-edge-colouring gives a coarse global division into red and blue edges, whereas a proper edge-colouring may use many colours and only forbids two incident edges from sharing a colour. That condition prevents immediate colour collisions at a vertex, but it does not by itself make a long cycle rainbow: nonadjacent edges on the same cycle can still receive the same colour. The theorem says that the colouring’s local constraint is enough to organize the entire vertex set into just two globally colour-distinct cycles.

What the Theorem Changes

The contribution is the partition requirement. Finding a rainbow cycle does not by itself show how to cover all remaining vertices with a second rainbow cycle. Requiring two cycles to be vertex-disjoint and collectively exhaustive couples those choices: the selected cycles must simultaneously avoid repeated colours within each cycle and cover every vertex exactly once.

The paper positions its result directly against the development of the original Lehel conjecture: a sufficiently-large-$n$ proof, later improvements, and the eventual all-$n$ resolution. Its conclusion is deliberately asymptotic rather than universal. The authors do not claim the rainbow statement for every order $n$ in the supplied abstract; they claim it once $n$ is sufficiently large.

Technical Scope

The theorem concerns complete graphs $K_n$. Completeness provides an edge between every pair of vertices, so the obstruction is not graph connectivity or missing adjacencies; it is selecting cycle edges that meet the rainbow condition while covering all vertices. Properness is equally central. At any vertex, incident edge colours are pairwise distinct, a structural condition that is much stronger than an arbitrary many-colour edge assignment but weaker than a prescribed global colour pattern.

The supplied abstract identifies the result as an existence theorem and does not provide an algorithm, a computational construction, or a numerical threshold for “sufficiently large.” The practical value is therefore conceptual and structural: it identifies a guarantee that future constructive work can target, rather than offering a procedure for producing the two cycles from a given colouring.

Evidence and Interpretation

For a combinatorics result of this kind, the relevant evidence is the proof rather than benchmark-style measurements. The claim is exact within its stated regime: two cycles, vertex-disjointness, full vertex coverage, rainbow edges within each cycle, and proper edge-colouring of a complete graph.

The result is a meaningful extension of the classical two-cycle phenomenon because it replaces two fixed monochromatic classes with potentially many colours while imposing distinctness inside both cycles. Still, its scope should not be overstated. The theorem is asymptotic, applies only to complete graphs with proper edge-colourings, and the available abstract does not state the threshold or whether an all-$n$ version is expected. Those boundaries matter: they leave open finite exceptional cases, non-complete host graphs, arbitrary edge-colourings, and constructive complexity.