Strengthened Brooks Theorem for digraphs of girth three

Details Strengthened Brooks Theorem for digraphs of girth three Strengthened Brooks Theorem for digraphs of girth three

2011-10-21

arxiv.org/abs/1110.4896v1

Mathematics

Combinatorics

12 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Strengthened Brooks Theorem for digraphs of girth three does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strengthened Brooks Theorem for digraphs of girth three, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strengthened Brooks Theorem for digraphs of girth three will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-563939