Stein's path-orientation conjecture for oriented graphs

Let GG be an oriented graph, and let 4δ0(G)44\delta^0(G)4 denote its minimum semidegree, the minimum of the in-degree and out-degree over all vertices. An oriented path of length \ell is an orientation of a path with \ell edges. Stein's conjecture. Every oriented graph GG contains all oriented paths of length 2δ0(G)12\delta^0(G)-1. The bound is best possible by considering disjoint unions of regular tournaments on 2δ0(G)12\delta^0(G)-1 vertices. The conjecture is supported by several partial results, including the directed-path case and cases with one change in direction, but its arbitrary-orientation case is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Yuping Gao and Allan Lo, “Long antipaths in oriented graphs”, arXiv:2607.24738 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.