On colouring oriented graphs of large girth

Abstract

We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^{\ast }$ along with a surjective homomorphism $\ddot{I}ˆ:V(D^{\ast })\to V(D)$ such that: (i) girth$(D^{\ast })\ge \ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^{\ast }$ to $C$ if and only if there exists a homomorphism from $D$ to $C$; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\ddot{I}†:V(D^{\ast })\to V(C)$ there exists a unique homomorphism $f:V(D)\to V(C)$ such that $\ddot{I}†=f\circ \ddot{I}ˆ$. Determining the oriented chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and oriented chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell \ge 3$ and $k\ge 5$, we include a construction of an oriented graph with girth $\ell$ and oriented chromatic number $k$.

10 pages, 0 figures, to be published in Contributions to Discrete Mathematics