ACYCLIC GRAPH-COLORING AND THE COMPLEXITY OF THE STAR CHROMATIC NUMBER

被引：35
|
作者：
GUICHARD, DR
机构：
[1] Whitman College Walla Walla, Washington
来源：
JOURNAL OF GRAPH THEORY | 1993年 / 17卷 / 02期
关键词：
D O I：
10.1002/jgt.3190170202
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, ''When is chi(star) < chi?'' We show that chi(star) < chi if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not in NP though it is both NP-hard and NP-easy.
引用
收藏
页码：129 / 134
页数：6
相关论文
共 50 条
12345