Alternating Paths in Oriented Graphs with Large Semidegree

  • Jozef Skokan
  • Mykhaylo Tyomkyn
DOI: https://doi.org/10.37236/13084

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.

Published
2025-11-03
Issue
Volume 32, Issue 4 (2025)
Article Number
P4.31