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 metadatas

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 : Thursday, February 7, 2019 - 3:25:30 PM
Document(s) archivé(s) le : Wednesday, December 1, 2010 - 2:51:13 AM

File

lehel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00512762, version 1

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, pp.176-180. ⟨lirmm-00512762⟩

Share

Metrics

Record views

260

Files downloads

215