Paths With Three Blocks In Digraphs

Abstract

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\ge k$ is established in any $(k+4)$-chromatic digraph. In general, we establish a quadratic bound for paths with three blocks.

7 pages