Bibliographic Details
| Title: |
Two-block paths in oriented graphs of large semidegree |
| Authors: |
Penev, Irena, Taruni, S, Thomassé, Stéphan, Trujillo-Negrete, Ana, Tyomkyn, Mykhaylo |
| Publication Year: |
2025 |
| Collection: |
Mathematics |
| Subject Terms: |
Mathematics - Combinatorics |
| More Details: |
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. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2503.23191 |
| Accession Number: |
edsarx.2503.23191 |
| Database: |
arXiv |
