Antidirected paths in oriented graphs
Antidirected paths in oriented graphs
We show that for any integer $k \ge 4$, every oriented graph with minimum semidegree bigger than $\frac{1}{2}(k-1+\sqrt{k-3})$ contains an antidirected path of length $k$. Consequently, every oriented graph on $n$ vertices with more than $(k-1+\sqrt{k-3})n$ edges contains an antidirected path of length $k$. This asymptotically proves the antidirected path version of a conjecture of Stein and of a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomass\'e, respectively.
Andrzej Grzesik、Marek Skrzypczyk
数学
Andrzej Grzesik,Marek Skrzypczyk.Antidirected paths in oriented graphs[EB/OL].(2025-06-13)[2025-07-16].https://arxiv.org/abs/2506.11866.点此复制
评论