Long antipaths and anticycles in oriented graphs (Q7016873)

Let \(\delta^{0}(D)\) be the minimum semi-degree of an oriented graph \(D\). \textit{B. Jackson} [J. Graph Theory 5, 145--157 (1981; Zbl 0458.05041)] proved that every oriented graph \(D\) with \(\delta^{0}(D)\geq k\) contains a directed path of length \(2k\) when \(|V (D)| > 2k +2\), and a directed Hamilton cycle when \(|V (D)| \leq 2k +2\). \textit{M. Stein} [Springer Optim. Appl. 165, 459--486 (2020; Zbl 1473.05055)] further conjectured that every oriented graph \(D\) with \(\delta^{0}(D) > k/2\) contains any orientated path of length \(k\). \textit{T. Klimošová} and \textit{M. Stein} [Discrete Math. 346, No. 9, Article ID 113515, 6 p. (2023; Zbl 1516.05109)] introduced the minimum pseudo-semidegree \(\overline{\delta^{0}}(D)\) (a slightly weaker variant of the minimum semi-degree condition) and showed that every oriented graph D with \(\overline{\delta^{0}}(D)\geq (3k-2)/4\) contains each antipath of length \(k\) for \(k \geq 3\). In this paper, the authors improve the result of Klimošová and Stein [loc. cit.] by showing that for all \(k \geq 2\), every oriented graph with \(\overline{\delta^{0}}(D)\geq (2k+1)/3\) contains either an antipath of length at least \(k +1\) or an anticycle of length at least \(k +1\). A conjecture proposed by Stein [loc. cit.] concludes the paper.