On the Length of Directed Paths in Digraphs
Yangyang Cheng, Peter Keevash
Source abstract
Abstract. Thomassé conjectured the following strengthening of the well-known Caccetta–Häaggkvist conjecture: any digraph with minimum out-degree [Formula: see text] and girth [Formula: see text] contains a directed path of length [Formula: see text]. Bai and Manoussakis [ SIAM J. Discrete Math., 33 (2019), pp. 2444–2451] gave counterexamples to Thomassé’s conjecture for every even [Formula: see text]. In this note, we first generalize their counterexamples to show that Thomassé’s conjecture is false for every [Formula: see text]. We also obtain the positive result that any digraph with minimum out-degree [Formula: see text] and girth [Formula: see text] contains a directed path of [Formula: see text]. For small [Formula: see text] we obtain better bounds; e.g., for [Formula: see text] we show that oriented graph with minimum out-degree [Formula: see text] contains a directed path of length [Formula: see text]. Furthermore, we show that each [Formula: see text]-regular digraph with girth [Formula: see text] contains a directed path of length [Formula: see text]. Our results give the first nontrivial bounds for these problems.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.