Strengthened Brooks' theorem for digraphs of girth at least three (Q640457)

Summary: 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 \textit{A. Johansson} [Asymptotic choice number for triangle free graphs, DIMACS Technical Report, 91--95 (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})\widetilde\Delta\), where \(\widetilde\Delta\) is the maximum geometric mean of the out-degree and in-degree of a vertex in \(D\), when \(\widetilde\Delta\) is sufficiently large. As a corollary it is proved that there exists an absolute constant \(\alpha< 1\) such that \(\chi(D)\leq\alpha(\widetilde\Delta+ 1)\) for every \(\widetilde\Delta> 2\).