Two results on the digraph chromatic number

It is known (Bollobás (1978) [4]; Kostochka and Mazurova (1977) [12]) that there exist graphs of maximum degree Δ and of arbitrarily large girth whose chromatic number is at least cΔ/logΔ. We show an analogous result for digraphs where the chromatic number of a digraph D is defined as the minimum in...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-05, Vol.312 (10), p.1823-1826
Main Authors: Harutyunyan, Ararat, Mohar, Bojan
Format: Article
Language:English
Subjects:
Chromatic number
Dichromatic number
Digraph
Digraph coloring
Girth
Graph theory
Graphs
Integers
Mathematical analysis
Veins
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is known (Bollobás (1978) [4]; Kostochka and Mazurova (1977) [12]) that there exist graphs of maximum degree Δ and of arbitrarily large girth whose chromatic number is at least cΔ/logΔ. 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 Erdős (1962) [5], that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2012.01.028