Alternating paths in oriented graphs with large semidegree
Skokan, J.
& Tyomkyn, M.
(2025).
Alternating paths in oriented graphs with large semidegree.
Electronic Journal of Combinatorics,
32(4).
https://doi.org/10.37236/13084
& Tyomkyn, M.
(2025).
Alternating paths in oriented graphs with large semidegree.
Electronic Journal of Combinatorics,
32(4).
https://doi.org/10.37236/13084
In new progress on conjectures of Stein, and Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, we prove that every oriented graph with all in- and out-degrees greater than 5k/8 contains an alternating path of length k. This improves on previous results of Klimošová and Stein, and Chen, Hou and Zhou.
