paper

Alternating paths in oriented graphs with large semidegree

arXiv:2406.03166

Abstract

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.

minor changes, bibliography updated, 7 pages, final version

Alternating paths in oriented graphs with large semidegree · wovepaper