ON THE LENGTH OF DIRECTED PATHS IN DIGRAPHS

Thomasse conjectured the following strengthening of the well-known Caccetta-Haaggkvist conjecture: any digraph with minimum out-degree delta and girth g contains a directed path of length delta(g - 1). Bai and Manoussakis [SIAM J. Discrete Math., 33 (2019), pp. 2444-2451] gave counterexamples to Thomasses conjecture for every even g geq 4. In this note, we first generalize their counterexamples to show that Thomasses conjecture is false for every g geq 4. We also obtain the positive result that any digraph with minimum out-degree delta and girth g contains a directed path of 2(1 - g2 ). For small g we obtain better bounds; e.g., for g = 3 we show that oriented graph with minimum out-degree delta contains a directed path of length 1.5delta. Furthermore, we show that each d-regular digraph with girth g contains a directed path of length Omega(dg/log d). Our results give the first nontrivial bounds for these problems. Copyright © by SIAM.