Strengthened Brooks Theorem for digraphs of girth three

Abstract

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)\le (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)\le \alpha (\tilde{\Delta }+1)$ for every $\tilde{\Delta }>2$.

12 pages

Cited by in corpus (2)

• Coloring tournaments: from local to global
• List coloring digraphs