Strengthened Brooks' theorem for digraphs of girth at least three

zbMATH Open1230.05129arXiv1110.4896MaRDI QIDQ640457FDOQ640457

Authors: Ararat Harutyunyan, Bojan Mohar 

Publication date: 18 October 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 (1996) shows that if $G$ is triangle-free, then the chromatic number drops to $O(Delta/logDelta)$. 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})ildeDelta$, where $ildeDelta$ is the maximum geometric mean of the out-degree and in-degree of a vertex in $D$, when $ildeDelta$ is sufficiently large. As a corollary it is proved that there exists an absolute constant $alpha<1$ such that $chi(D)leqalpha(ildeDelta+1)$ for every $ildeDelta>2$.

Full work available at URL: https://arxiv.org/abs/1110.4896

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Two results on the digraph chromatic number
• A note on coloring digraphs of large girth
• Digraph girth via chromatic number
• On Brooks' Theorem for Sparse Graphs
• The \(m\)-degenerate chromatic number of a digraph

zbMATH Keywords

digraph coloringdichromatic numberBrooks theoremdigonsparse digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cited In (12)

• Hajós and Ore constructions for digraphs
• The \(m\)-degenerate chromatic number of a digraph
• Two results on the digraph chromatic number
• Coloring digraphs with forbidden cycles
• A note on coloring digraphs of large girth
• Digraphs and variable degeneracy
• Extendiendo un resultado de coloraciones de gráficas a coloraciones de digráficas
• The minimum number of edges in 4-critical digraphs of given order
• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
• Digraph girth via chromatic number
• Coloring tournaments: from local to global
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth

This page was built for publication: Strengthened Brooks' theorem for digraphs of girth at least three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640457)