On colouring oriented graphs of large girth
Preprint
Abstract
We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $ψ\colon V(D^*) \to V(D)$ such that: (i) girth$(D^*) \geq\ell$; (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 $\varphi\colon V(D^*) \to V(C)$ there exists a unique homomorphism $f\colon V(D) \to V(C)$ such that $\varphi=f \circ ψ$. 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\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and oriented chromatic number $k$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A short construction of highly chromatic digraphs without short cyclesContributions to Discrete Mathematics, 2015
- The circular chromatic number of a digraphJournal of Graph Theory, 2004
- On sparse graphs with given colorings and homomorphismsJournal of Combinatorial Theory, Series B, 2004
- Ahypergraph-free construction of highly chromatic graphs without short cyclesCombinatorica, 1989
- Uniquely Colourable Graphs with Large GirthCanadian Journal of Mathematics, 1976
- On chromatic number of finite set-systemsActa Mathematica Hungarica, 1968
- Graph Theory and ProbabilityCanadian Journal of Mathematics, 1959