Lehel's cycle partition conjecture

Let GG be a graph, and let G\overline G denote its complement. Lehel's conjecture. The vertices of GG can be covered by a cycle C1C_1 in GG and a vertex-disjoint cycle C2C_2 in G\overline G. This is a two-colour cycle-partition problem for complete graphs and is presented as a motivation for studying sparse complements of cycles; the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Alexey Pokrovskiy, “Partitioning a graph into a cycle and a sparse graph”, arXiv:1607.03348 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.