|国家预印本平台
首页|Antidirected paths in oriented graphs

Antidirected paths in oriented graphs

Antidirected paths in oriented graphs

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论