


















Thomassé conjectured the following strengthening of the well-known Caccetta-Haggkvist Conjecture: any digraph with minimum out-degree $δ$ and girth $g$ contains a directed path of length $δ(g-1)$. Bai and Manoussakis \cite{Bai} gave counterexamples to Thomassé's conjecture for every even $g\geq 4$. In this note, we first generalize their counterexamples to show that Thomassé's conjecture is false for every $g\geq 4$. We also obtain the positive result that any digraph with minimum out-degree $δ$ 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 $δ$ contains a directed path of length $1.5δ$. Furthermore, we show that each $d$-regular digraph with girth $g$ contains a directed path of length $Ω(dg/\log d)$. Our results give the first non-trivial bounds for these problems.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。