Premium
Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments
Author(s) -
BangJensen Jørgen,
Bessy Stéphane,
Thomassé Stéphan
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21740
Subject(s) - tournament , mathematics , conjecture , combinatorics , disjoint sets , digraph , degree (music) , vertex (graph theory) , discrete mathematics , graph , physics , acoustics
We prove that every tournament with minimum out‐degree at least 2 k − 1 contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree 2 k − 1 contains k vertex disjoint cycles. We also prove that for every ε > 0 , when k is large enough, every tournament with minimum out‐degree at least ( 1.5 + ε ) k contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.