Two-block paths in oriented graphs of large semidegree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913766241730560 |
|---|---|
| author | Penev, Irena Taruni, S Thomassé, Stéphan Trujillo-Negrete, Ana Tyomkyn, Mykhaylo |
| author_facet | Penev, Irena Taruni, S Thomassé, Stéphan Trujillo-Negrete, Ana Tyomkyn, Mykhaylo |
| contents | We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes $\ell$ and $k-\ell$. As a corollary, we show that every oriented graph with all in- and out-degrees at least $3k/4$ contains every two-block path with $k$ arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23191 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-block paths in oriented graphs of large semidegree Penev, Irena Taruni, S Thomassé, Stéphan Trujillo-Negrete, Ana Tyomkyn, Mykhaylo Combinatorics We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes $\ell$ and $k-\ell$. As a corollary, we show that every oriented graph with all in- and out-degrees at least $3k/4$ contains every two-block path with $k$ arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths. |
| title | Two-block paths in oriented graphs of large semidegree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.23191 |