2011/10/21 by Ararat Harutyunyan, Harutyunyan, Ararat, Bojan Mohar +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1110.4896
openalex publication_date 2011/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Brooks' Theorem states that a connected graph G of maximum degree Δ has chromatic number at most Δ, 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(Δ/ log Δ). 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 χ(D) ≤ (1-e-13) Δ, where Δ is the maximum geometric mean of the out-degree and in-degree of a vertex in D, when Δ is sufficiently large. As a corollary it is proved that there exists an absolute constant α< 1 such that χ(D) ≤ α(Δ + 1) for every Δ > 2.