Lehel's cycle partition conjecture
Let be a graph, and let denote its complement. Lehel's conjecture. The vertices of can be covered by a cycle in and a vertex-disjoint cycle in .
References
Status
- Solved: Stéphane Bessy and Stéphan Thomassé. Partitioning a graph into a cycle and an anticycle, a proof of Lehel’s conjecture (Journal of Combinatorial Theory, Series B, 2010) https://www.sciencedirect.com/science/article/pii/S0095895609000604
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.