Skip to Main content Skip to Navigation
Journal articles

Partitioning a Graph into a Cycle and an Anticycle: A Proof of Lehel's Conjecture

Stéphane Bessy 1 Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We prove that every graph $G$ has a vertex partition into a cycle and an anticyle (a cycle in the complement of $G$). Emptyset, singletons and edges are considered as cycles. This problem was posed by Lehel and shown to be true for very large graphs by \L uczak, Rödl and Szemerédi~\cite{LRS}, and more recently for large graphs by Allen~\cite{PA}.
Document type :
Journal articles
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512762
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:24:51 PM
Last modification on : Wednesday, June 30, 2021 - 12:17:07 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:51:13 AM

File

lehel.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Stéphane Bessy, Stéphan Thomassé. Partitioning a Graph into a Cycle and an Anticycle: A Proof of Lehel's Conjecture. Journal of Combinatorial Theory, Series B, Elsevier, 2010, 100 (2), pp.176-180. ⟨10.1016/j.jctb.2009.07.001⟩. ⟨lirmm-00512762⟩

Share

Metrics

Record views

298

Files downloads

265