Two‐Block Paths in Oriented Graphs of Large Semidegree

Abstract

ABSTRACT 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 and with , we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes and . As a corollary, we show that every oriented graph with all in‐ and out‐degrees at least contains every two‐block path with arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths.