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}.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2010, 100, pp.176-180
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512762
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:24:51
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:51:13

Fichier

lehel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

82