Back to Search Start Over

Antipaths in oriented graphs

Authors :
Klimošová, Tereza
Stein, Maya
Publication Year :
2022

Abstract

We show that for any natural number $k \ge 1$, any oriented graph $D$ of minimum semidegree at least $(3k- 2)/4$ contains an antidirected path of length $k$. In fact, a slightly weaker condition on the semidegree sequence of $D$ suffices, and as a consequence, we confirm a weakened antidirected path version of a conjecture of Addario-Berry, Havet, Linhares Sales, Thomass\'e and Reed.<br />Comment: Fixed an accidental omission in Problem 10

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2212.09876
Document Type :
Working Paper