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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2014, 75 (3), pp.284-302. 〈10.1002/jgt.21740〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01282882
Contributeur : Stéphane Bessy <>
Soumis le : vendredi 4 mars 2016 - 15:03:06
Dernière modification le : jeudi 7 février 2019 - 16:21:22

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

338