Strengthened Brooks' theorem for digraphs of girth at least three

Ararat Harutyunyan ; Bojan Mohar

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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$.

Détail

DOI : 10.37236/682

Classification : 05C15, 05C20
Mots-clés : digraph coloring, dichromatic number, Brooks theorem, digon, sparse digraph