On the Number of Vertex-Disjoint Cycles in Digraphs

Source 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. This conjecture is famous as one of a hundred unsolved problems selected in [A. Bondy and M. R. Murty, Graph Theory, Springer-Verlag, London, 2008]. Lichiardopol, Pór, and Sereni proved in [ SIAM J. Discrete Math., 23 (2009), pp. 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 (2014), pp. 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 2006 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 paper, 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é.