Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments

Jørgen Bang-Jensen 1 Stéphane Bessy 2 Stéphan Thomassé 3
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We prove that every tournament with minimum out-degree at least inline image contains k disjoint 3-cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out-degree inline image contains k vertex disjoint cycles. We also prove that for every inline image, when k is large enough, every tournament with minimum out-degree at least inline image contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01282882
Contributor : Stéphane Bessy <>
Submitted on : Friday, March 4, 2016 - 3:03:06 PM
Last modification on : Wednesday, April 3, 2019 - 1:30:18 AM

Links full text

Identifiers

Citation

Jørgen Bang-Jensen, Stéphane Bessy, Stéphan Thomassé. Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments. Journal of Graph Theory, Wiley, 2014, 75 (3), pp.284-302. ⟨10.1002/jgt.21740⟩. ⟨lirmm-01282882⟩

Share

Metrics

Record views

372