Stein's path-orientation conjecture for oriented graphs

Less than 1 year old · traced to

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.

References

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.