Quantcast

On the Number of Vertex-Disjoint Cycles in Digraphs

Research paper by Yandong Bai, Yannis Manoussakis

Indexed on: 09 Jan '20Published on: 10 Dec '19Published in: SIAM Journal on Discrete Mathematics



Abstract

SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2444-2451, January 2019. 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é.