2021/10/19 by Mortada, Maidoun, Sahili, Amine El, Mohsen, Zahraa
#05C07 #05C15 #05C20 #05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.09933
A path with three blocks P(k,l,r) is an oriented path formed by k-forward arcs followed by l-backward arcs then r-forward arcs. We prove that any (2k+1)-chromatic digraph contains a path P(1,k,1). However the existence of P(1,l,1) with l ≥ k is established in any (k+4)-chromatic digraph. In general, we establish a quadratic bound for paths with three blocks.