On the length of directed paths in digraphs

Abstract

Thomassé conjectured the following strengthening of the well-known Caccetta-Haggkvist Conjecture: any digraph with minimum out-degree $\hat{I}´$ and girth $g$ contains a directed path of length $\hat{I}´(g-1)$. Bai and Manoussakis \cite{Bai} gave counterexamples to Thomassé's conjecture for every even $g\ge 4$. In this note, we first generalize their counterexamples to show that Thomassé's conjecture is false for every $g\ge 4$. We also obtain the positive result that any digraph with minimum out-degree $\hat{I}´$ and girth $g$ contains a directed path of $2(1-\frac{2}{g})$. For small $g$ we obtain better bounds, e.g.~for $g=3$ we show that oriented graph with minimum out-degree $\hat{I}´$ contains a directed path of length $1.5\hat{I}´$. Furthermore, we show that each $d$-regular digraph with girth $g$ contains a directed path of length $\hat{I}\text{c◯}(dg/\log d)$. Our results give the first non-trivial bounds for these problems.