2025/03/29 by Irena Penev, Penev, Irena, S Taruni +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO
paper · pdf · doi:10.48550/arxiv.2503.23191
arxiv created 2026/08/01 · arxiv updated 2026/08/04
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 ℓ with k/2≤ ℓ < k, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes ℓ and k-ℓ. 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.