摘要
图的条件色数是经典色数的推广。确定图的条件色数问题是一个NPC问题。已知广义Petersen图的3-条件色数的上界是8。证明了广义Petersen图3-条件色数的下界是4,并刻画了达到此下界的广义Petersen图。
The condition chromatic number of a graph is a generalization of classic chromatic number. It is NP- complete to determine condition chromatic numbers of graphs. The upper bound of the 3-condition chromatic num- ber of the generalized Petersen graph is 8. It is proved that the lower bound of the 3-condition chromatic number of the generalized Petersen graph is 4, and this generalized Petersen graph is characterized.
出处
《科学技术与工程》
北大核心
2012年第5期975-977,981,共4页
Science Technology and Engineering
基金
国家自然科学基金(10671076
11071089)
中央高校基本科研业务费专项资金(21611610)
广东省自然科学基金(10151063201000005)资助
关键词
广义PETERSEN图
条件着色
条件色数
generalized Petersen graph conditional coloring conditional chromatic number
