| 直径为2的图的P2路色问题 |
| |
| 引用本文： | 原晋江,康丽英.直径为2的图的P2路色问题[J].数学杂志,1995,15(4):401-404. |
| |
| 作者姓名： | 原晋江 康丽英 |
| |
| 作者单位： | 郑州大学，石家庄铁道学院 |
| |
| 摘 要： | 一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题。已知对于直径为２的图及任意给定的整数ｒ≥３，图的（２，ｒ）路色数问题是ＮＰ－完全的。本文给出直径为２的（２，２）路色图的一个好的刻划，并由此给出该问题的一个多项式时间算法，从而解决了以ｒ为参数的直径为２的图的（２，ｒ）路色数问题的计算复杂性分类。
|
| 关 键 词： | 图 着色 路色数 直径 平面图 |
P_2PATH COLORKING PTOBLEM OF GTAPHS WITH DIAMETER TWO |
| |
| Yuan Jinjiang.P_2PATH COLORKING PTOBLEM OF GTAPHS WITH DIAMETER TWO[J].Journal of Mathematics,1995,15(4):401-404. |
| |
| Authors: | Yuan Jinjiang |
| |
| Abstract: | |
| |
| Keywords: | Graph Cloring Path Chromatic number |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
