# The Bermond-Thomassen Conjecture

 Importance: Medium ✭✭
 Author(s): Bermond, Jean-Claude Thomassen, Carsten
 Subject: Graph Theory » Directed Graphs
 Keywords: cycles
 Posted by: JS on: October 1st, 2007
Conjecture   For every positive integer , every digraph with minimum out-degree at least contains disjoint cycles.

This conjecture is a simple observation when . It was proved by Thomassen~[Tho83] in 1983 when , and more recently the case was settled~[LPS07].

The bound offered would be optimal — just consider a symmetric complete graph on vertices. In 1996, Alon~[Alo96] proved that the statement is true with replaced by . The conjecture was also verified for tournaments of minimum in-degree at least ~[BLS07].

Bang-Jensen et al. [BBT] made a stronger conjecture for digraph with sufficiently large girth.

Conjecture   For every integer , every digraph with girth at least and with minimum out-degree at least contains disjoint cycles.

The constant is best possible. Indeed, for every integers and , consider the digraph on vertices with vertex set and arc set . It has girth and out-degree . Moreover, for , the digraph admits a partition into vertex disjoint 3-cycles and no more. For g = 3, the first case of this conjecture which differs from Bermond-Thomassen Conjecture and which is not already known corresponds to the following question:

Question   Does every digraph D without 2-cycles and out-degree at least 6 admit four vertex disjoint cycles?

## Bibliography

[Alo96] N. Alon: Disjoint directed cycles, J. Combin. Theory Ser. B, 68(2):167--178, 1996. PDF

[BBT] J. Bang-Jensen, S. Bessy and S. Thomassé, Disjoint 3-cycles in tournaments: a proof of the Bermond-Thomassen conjecture for tournaments, J. Graph Theory, to appear.

*[BeTh81] J.-C. Bermond and C.~Thomassen: Cycles in digraphs---a survey, J. Graph Theory, 5(1):1--43, 1981. MathSciNet

[BLS07] S.~Bessy, N.~Lichiardopol, and J.-S. Sereni: Two proofs of the {B}ermond-{T}homassen conjecture for tournaments with bounded minimum in-degree, Discrete Math., Special Issue dedicated to CS06, to appear.

[LPS07] N.~Lichiardopol, A.~ P\'or, and J.-S. Sereni: A step towards the Bermond-Thomassen conjecture about disjoint cycles in digraphs, Submitted, 2007.

[Tho83] C.~Thomassen, Disjoint cycles in digraphs, Combinatorica, 3(3-4):393--396, 1983. MathSciNet

* indicates original appearance(s) of problem.