Alternating Paths in Oriented Graphs with Large Semidegree
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.
Authors
- Jozef Skokan (ORCID: https://orcid.org/0000-0003-3996-7676)
- Mykhaylo Tyomkyn
Institutions
- Charles University (CZ)
- London School of Economics and Political Science (GB)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-11-03
- DOI
- https://doi.org/10.37236/13084
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00