Quantcast

On the number of vertex-disjoint cycles in digraphs

Research paper by Yandong Bai, Yannis Manoussakis

Indexed on: 08 May '18Published on: 08 May '18Published in: arXiv - Mathematics - Combinatorics



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\'{e} conjectured in [J. Graph Theory 75 (3) (2014) 284-302] that every digraph with minimum outdegree at least $\frac{g}{g-1}k$ contains $k$ vertex-disjoint cycles. 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\'{e} by constructing a family of counterexamples.