Strengthened Brooks' theorem for digraphs of girth at least three

MaRDI QIDQ640457zbMATH OpenFDO

Authors Ararat Harutyunyan, Bojan Mohar

Publication date 18 October 2011

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

Full work available at URL https://arxiv.org/abs/1110.4896, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p195.html

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

zbMATH Keywords

digraph coloringdichromatic numberBrooks theoremdigonsparse digraph

Mathematics Subject Classification ID

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

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$.

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

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)