Stein's path-orientation conjecture for oriented graphs
Stein's path-orientation conjecture for oriented graphs
Let be an oriented graph, and let denote its minimum semidegree, the minimum of the in-degree and out-degree over all vertices. An oriented path of length is an orientation of a path with edges. Stein's conjecture. Every oriented graph contains all oriented paths of length . The bound is best possible by considering disjoint unions of regular tournaments on 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.