Strengthened Brooks' Theorem for Digraphs of Girth at least Three
Ararat Harutyunyan, Bojan Mohar · The Electronic Journal of Combinatorics · 2011
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011
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 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$.
Open the resolved locator · 10.37236/682
Metadata licence: OpenAlex metadata (CC0)