Strengthened Brooks' Theorem for Digraphs of Girth at least Three
Strengthened Brooks' Theorem for Digraphs of Girth at least Three
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 …