Paths with Two Blocks in Oriented Graphs of Large Minimum Semi-Degree

Abstract

Stein (2020) conjectured that for any positive integer $k$, every oriented graph of minimum semi-degree greater than $k/2$ contains every oriented path of length $k$. This conjecture is true by a result from Jackson (JGT, 1981), where he demonstrated that every oriented graph of minimum semi-degree at least $k/2$ includes a directed path of length $k$. In this paper, we establish the validity of Stein's conjecture specifically for any oriented path with two blocks, where, a block of an oriented path $P$ refers to a maximal directed subpath within $P$.