A Step toward the Bermond–Thomassen Conjecture about Disjoint Cycles in Digraphs
Authors:
- Nicolas LichiardopolNLNicolas Lichiardopol
- Attila PórAPAttila Pór
- Jean-Sébastien SereniJSJean-Sébastien Sereni
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 23 (2) , 979-992
Abstract
In 1981, Bermond and Thomassen conjectured that every digraph with minimum out-degree at least $2k-1$ contains k disjoint cycles. This conjecture is trivial for $k=1$, and was established for $k=2$ by Thomassen in 1983. We verify it for the next case, proving that every digraph with minimum out-degree at least five contains three disjoint cycles. To show this, we improve Thomassen's result by proving that every digraph whose vertices have out-degree at least three, except at most two with out-degree two, indeed contains two disjoint cycles.
Keywords
This publication has 4 references indexed in Scilit:
- Two proofs of Bermond-Thomassen conjecture for regular tournamentsElectronic Notes in Discrete Mathematics, 2007
- Disjoint Directed CyclesJournal of Combinatorial Theory, Series B, 1996
- Disjoint cycles in digraphsCombinatorica, 1983
- Cycles in digraphs– a surveyJournal of Graph Theory, 1981