贪心消着色数与Grundy数

北京邮电大学学报 ›› 1999, Vol. 22 ›› Issue (4): 14-19.

贪心消着色数与Grundy数

孙惠泉

北京邮电大学信息工程系, 北京 100876

收稿日期:1999-05-18 出版日期:1999-11-10

Greedy Colouring and Grundy Number

Sun Huiquan

Department of Information Engineering, Beijing University of Posts and Telecommunications, Beijing 100876

Received:1999-05-18 Online:1999-11-10

摘要/Abstract

摘要： 主要讨论贪心着色与Grundy数的关系.证明了求Grundy数问题是个NP-hard问题, 引入并讨论了随意可着色图的概念及其相关性质, 并证明识别随意可着色图是个NP-hard问题.

关键词: Grundy数, 贪心着色数, 随意可着色图

Abstract: We discuss the relationship between greedy colouringand Grundy number, and we prove that finding Grundy number of a graph is an NP-hard problem.We also introduce the concept of randomly colourable graphs, implore some properties of them and prove that recognizing a graph to be randomly colourable is an NP-hard problem.

Key words: greedy colouring, Grundy number, randomly colourable graph

中图分类号:

O151

孙惠泉. 贪心消着色数与Grundy数[J]. 北京邮电大学学报, 1999, 22(4): 14-19.

Sun Huiquan. Greedy Colouring and Grundy Number[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 1999, 22(4): 14-19.

[1]	欧智明,韩书琴. 阶数为素数幂的一类整循环矩阵[J]. 北京邮电大学学报, 1998, 21(1): 7-11.
[2]	黄铮1, 丁金扣1, 温巧燕1, 杨义先2. 构造GF(2)~n的t-正交分划的递归生成算法[J]. 北京邮电大学学报, 2003, 26(S1): 57-59.