Antidirected paths in oriented graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909648555081728 |
|---|---|
| author | Grzesik, Andrzej Skrzypczyk, Marek |
| author_facet | Grzesik, Andrzej Skrzypczyk, Marek |
| contents | 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é, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11866 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Antidirected paths in oriented graphs Grzesik, Andrzej Skrzypczyk, Marek Combinatorics 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é, respectively. |
| title | Antidirected paths in oriented graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.11866 |