Ararat Harutyunyan

It is known (Bollob\'{a}s (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree $\Delta$ and of arbitrarily large girth whose chromatic number is at least $c \Delta / \log \Delta$. We show an analogous result for digraphs where the chromatic number of a digraph $D$ is defined as the minimum integer $k$ so that $V(D)$ can be partitioned into $k$ acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdos (1962), that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.

Brooks' Theorem states that a connected graph $G$ of maximum degree $\Delta$ has chromatic number at most $\Delta$, unless $G$ is an odd cycle or a complete graph. A result of Johansson (1996) shows that if $G$ is triangle-free, then the chromatic number drops to $O(\Delta / \log \Delta)$. In this paper, we derive a weak analog for the chromatic number of digraphs. We show that every (loopless) digraph $D$ without directed cycles of length two has chromatic number $\chi(D) \leq (1-e^{-13}) \tilde{\Delta}$, where $\tilde{\Delta}$ is the maximum geometric mean of the out-degree and in-degree of a vertex in $D$, when $\tilde{\Delta}$ is sufficiently large. As a corollary it is proved that there exists an absolute constant $\alpha < 1$ such that $\chi(D) \leq \alpha (\tilde{\Delta} + 1)$ for every $\tilde{\Delta} > 2$.

Let C and D be digraphs. A mapping $f:V(D)\to V(C)$ is a C-colouring if for every arc $uv$ of D, either $f(u)f(v)$ is an arc of C or $f(u)=f(v)$, and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number $r\geq 1$, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.

Brooks' Theorem states that a connected graph $G$ of maximum degree $\Delta$ has chromatic number at most $\Delta$, unless $G$ is an odd cycle or a complete graph. A result of Johansson shows that if $G$ is triangle-free, then the chromatic number drops to $O(\Delta / \log \Delta)$. In this paper, we derive a weak analog for the chromatic number of digraphs. We show that every (loopless) digraph $D$ without directed cycles of length two has chromatic number $\chi(D) \leq (1-e^{-13}) \tilde{\Delta}$, where $\tilde{\Delta}$ is the maximum geometric mean of the out-degree and in-degree of a vertex in $D$, when $\tilde{\Delta}$ is sufficiently large. As a corollary it is proved that there exists an absolute constant $\alpha < 1$ such that $\chi(D) \leq \alpha (\tilde{\Delta} + 1)$ for every $\tilde{\Delta} > 2$.