arXiv Open Access 2025

Two-block paths in oriented graphs of large semidegree

Irena Penev S Taruni Stéphan Thomassé Ana Trujillo-Negrete Mykhaylo Tyomkyn

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

math.CO

Penulis (5)

Irena Penev

S Taruni

Stéphan Thomassé

Ana Trujillo-Negrete

Mykhaylo Tyomkyn

Format Sitasi

APA MLA BibTeX

Penev, I., Taruni, S., Thomassé, S., Trujillo-Negrete, A., Tyomkyn, M. (2025). Two-block paths in oriented graphs of large semidegree. https://arxiv.org/abs/2503.23191

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓