Partitioning a Graph into a Cycle and an Anticycle: A Proof of Lehel's Conjecture - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Combinatorial Theory, Series B Year : 2010

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

Stéphane Bessy
Stéphan Thomassé

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}.
Fichier principal
Vignette du fichier
lehel.pdf (118.4 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00512762 , version 1 (31-08-2010)

Identifiers

Cite

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, 2010, 100 (2), pp.176-180. ⟨10.1016/j.jctb.2009.07.001⟩. ⟨lirmm-00512762⟩
138 View
185 Download

Altmetric

Share

Gmail Facebook X LinkedIn More