On the number of vertex-disjoint cycles in digraphs

Abstract

Let $k$ be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex-disjoint cycles. It is famous as one of the one hundred unsolved problems selected in [Bondy, Murty, Graph Theory, Springer-Verlag London, 2008]. Lichiardopol, Por and Sereni proved in [SIAM J. Discrete Math. 23 (2) (2009) 979-992] that the above conjecture holds for $k=3$. Let $g$ be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy and Thomassé conjectured in [J. Graph Theory 75 (3) (2014) 284-302] that every digraph with girth $g$ and minimum outdegree at least $\frac{g}{g-1}k$ contains $k$ vertex-disjoint cycles. Thomassé conjectured around 2005 that every oriented graph (a digraph without 2-cycles) with girth $g$ and minimum outdegree at least $h$ contains a path of length $h(g-1)$, where $h$ is a positive integer. In this note, we first present a new shorter proof of the Bermond-Thomassen conjecture for the case of $k=3$, and then we disprove the conjecture proposed by Bang-Jensen, Bessy and Thomassé. Finally, we disprove the even girth case of the conjecture proposed by Thomassé.