Two proofs of Bermond-Thomassen conjecture for regular tournaments

Stéphane Bessy 1 Jean-Sébastien Sereni 2 Nicolas Lichiardopol 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Bermond-Thomassen conjecture says that a digraph of minimum out-degree at least 2r−1, r >=1, contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, but it is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for regular tournaments. In the first one, we shall prove auxiliary results about union of sets contained in other union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.
Type de document :
Communication dans un congrès
6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Jul 2007, Prague, République Tchèque, Czech Republic. Elsevier, 28, pp.47-53, 2007, Electronic Notes in Discrete Mathematics. <http://kam.mff.cuni.cz/~cs06/>. <10.1016/j.endm.2007.01.008>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00153984
Contributeur : Stephan Thomasse <>
Soumis le : mardi 12 juin 2007 - 14:42:38
Dernière modification le : vendredi 9 juin 2017 - 10:42:48

Identifiants

Collections

Citation

Stéphane Bessy, Jean-Sébastien Sereni, Nicolas Lichiardopol. Two proofs of Bermond-Thomassen conjecture for regular tournaments. 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Jul 2007, Prague, République Tchèque, Czech Republic. Elsevier, 28, pp.47-53, 2007, Electronic Notes in Discrete Mathematics. <http://kam.mff.cuni.cz/~cs06/>. <10.1016/j.endm.2007.01.008>. <lirmm-00153984>

Partager

Métriques

Consultations de la notice

170