Two results on the digraph chromatic number
Two results on the digraph chromatic number
复制标题
有向图色数的两个结果
DOI：
10.1016/j.disc.2012.01.028
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
B. Mohar
中科院分区：
文献类型：
--
作者：
Ararat Harutyunyan;B. Mohar
已知（Bollobás（1978）[4]; Kostochka and Mazurova（1977）[12]）存在最大度为Δ且围长任意大的图，其色数至少为cΔ/logΔ。我们证明了一个类似的结果，其中有向图D的色数被定义为最小整数k，使得V（D）可以被划分为k个无圈集，围长是相应的无向图中最短圈的长度。本文还证明了，与Erdans（1962）[5]的一个旧结果相同，存在色数任意大的有向图，其中每个顶点的大子集都是2-可染的。
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.