ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH

We prove that for every oriented graph D and every choice of positive integers k and ℓ, there exists an oriented graph D^∗ along with a surjective homomorphism ψ: V (D^∗) → V (D) such that: (i) girth(D^∗) ≥ ℓ; (ii) for every oriented graph C with at most k vertices, there exists a homomorphism from D^∗ 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 φ: V (D^∗) → V (C) there exists a unique homomorphism f : V (D) → V (C) such that φ = f ◦ ψ. 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 ℓ ≥ 3 and k ≥ 5, we include a construction of an oriented graph with girth ℓ and oriented chromatic number k.