Long antipaths and anticycles in oriented graphs

Abstract

Let ${\delta }^0(D)$ be the minimum semi-degree of an oriented graph $D$. Jackson (1981) proved that every oriented graph $D$ with ${\delta }^0(D)\ge k$ contains a directed path of length $2k$ when $|V(D)|>2k+2$, and a directed Hamilton cycle when $|V(D)|\le 2k+2$. Stein~(2020) further conjectured that every oriented graph $D$ with ${\delta }^0(D)>k/2$ contains any orientated path of length $k$. Recently, Klimousová and Stein (DM, 2023) introduced the minimum pseudo-semi-degree ${\tilde{\delta }}^0(D)$ (a slight weaker than the minimum semi-degree condition as ${\tilde{\delta }}^0(D)\ge {\delta }^0(D))$ and showed that every oriented graph $D$ with ${\tilde{\delta }}^0(D)\ge (3k-2)/4$ contains each antipath of length $k$ for $k\ge 3$. In this paper, we improve the result of Klimousová and Stein by showing that for all $k\ge 2$, every oriented graph with ${\tilde{\delta }}^0(D)\ge (2k+1)/3$ contains either an antipath of length at least $k+1$ or an anticycle of length at least $k+1$. Furthermore, we answer a problem raised by Klimousová and Stein in the negative.

11 pages