Stein's conjecture on oriented paths in graphs of large semidegree
Stein's conjecture on oriented paths in graphs of large semidegree
Let be an oriented graph, let denote its minimum semidegree, and let be a nonnegative integer. An orientation of the -edge path is an oriented graph obtained by assigning a direction to each edge of an undirected path with edges. Stein's conjecture. Every oriented graph with minimum semidegree contains every orientation of the -edge path.
Jackson's theorem proves the directed-path case. Stein and Trujillo-Negrete proved the conjecture for oriented graphs containing no oriented -cycle, while the general statement remains open; the paper studies two-block paths as a step toward it.
Sources & referencesView supporting material
Primary source
Irena Penev, S Taruni, Stéphan Thomassé, Ana Trujillo-Negrete and Mykhaylo Tyomkyn, “Two-block paths in oriented graphs of large semidegree”, arXiv:2503.23191 (2026).
Additional references
2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2406.03166.
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.