Alternating Paths in Oriented Graphs with Large Semidegree
Jozef Skokan, Mykhaylo Tyomkyn · The Electronic Journal of Combinatorics · 2025
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.