Two results on the digraph chromatic number

Details Two results on the digraph chromatic number Two results on the digraph chromatic number

2011-10-21

arxiv.org/abs/1110.4898v1

Mathematics

Combinatorics

Scientific paper

It is known (Bollob\'{a}s (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree $\Delta$ and of arbitrarily large girth whose chromatic number is at least $c \Delta / \log \Delta$. We show an analogous result for digraphs where the chromatic number of a digraph $D$ is defined as the minimum integer $k$ so that $V(D)$ can be partitioned into $k$ acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdos (1962), that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.

Affiliated with

Also associated with

No associations

Rating

Two results on the digraph chromatic number 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 Two results on the digraph chromatic number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two results on the digraph chromatic number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-563949