![](/files/happy5.png)
The Bermond-Thomassen Conjecture
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ 2k-1 $](/files/tex/7dee0e3b6c6462122fea33090b927b7d6e36817a.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
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.
![$ g >1 $](/files/tex/7b4b714c716128546cd31bff0cd7acb005515666.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ \frac{g}{g-1}k $](/files/tex/dcbe693a39ced2b2fd3254ebe51b65fe57597cde.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
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:
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.