| 广义Petersen图条件色数的最好下界 |
| |
| 引用本文： | 李苏,樊锁海.广义Petersen图条件色数的最好下界[J].科学技术与工程,2012,12(5):975-977,981. |
| |
| 作者姓名： | 李苏 樊锁海 |
| |
| 作者单位： | 暨南大学信息科学技术学院,广州,510632 |
| |
| 基金项目： | 国家自然科学基金(10671076, 11071089);中央高校基本科研业务费专项资金(21611610);广东省自然科学基金(10151063201000005) |
| |
| 摘 要： | 图的条件色数是经典色数的推广，确定图的条件色数问题是一个NPC问题。已知广义Petersen图的3-条件色数的上界是8。证明了广义Petersen图3-条件色数的下界是4，并刻画了达到此下界的广义Petersen图。
|
| 关 键 词： | 广义Petersen图 条件着色 条件色数 |
| 收稿时间： | 2011/11/21 0:00:00 |
| 修稿时间： | 2011/11/28 0:00:00 |
The best lower bound of conditional chromatic number of the generalized Petersen graphs |
| |
| Li Su.The best lower bound of conditional chromatic number of the generalized Petersen graphs[J].Science Technology and Engineering,2012,12(5):975-977,981. |
| |
| Authors: | Li Su |
| |
| Institution: | (College of Information Science and Technology,Jinan University,Guangzhou 510632,P.R.China) |
| |
| Abstract: | 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 number 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. |
| |
| Keywords: | generalized Petersen graph conditional coloring conditional chromatic number |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《科学技术与工程》浏览原始摘要信息 |
| 点击此处可从《科学技术与工程》下载免费的PDF全文 |
