图的路色数问题的NP－完全性  

The NP-completeness of The Path Chromatic Number Problem of Graphs

作　　者：原晋江[1] 

机构地区：[1]郑州大学数学系

出　　处：《数学研究》1995年第1期49-53,共5页Journal of Mathematical Study

基　　金：国家自然科学基金

摘　　要：一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题．本文研究其算法复杂性，并得到以下结果：对于任意给定的ｋ，２≤ｋ≤∞，图的（ｋ，２）路色数问题及直径为２的图的（ｋ，３）路色数问题都是ＮＰ－完全的；对于任意给定的ｋ，２≤ｋ≤∞，平面图的（ｋ，３）路色数问题也是ＮＰ－完全的．Is there a normal Pk coloring using r colors for a given graph? This problem is called as the (k,r) path chromatic number problem of graphs. This paper studies the computational complexity of this problem, and obtains the following results: For any given integer k, 2≤k≤∞.the (k,2) path chromatic number problem for graphs and the (k,3) path chromatic number problem for graphs with diameter 2 are NP-complete ; For any given integer k,2≤k≤∞.the (k,3) path chromatic number problem for planar graphs is also NP-complete.

关 键 词：路色数 NP-完全性 图论 点色数 

分 类 号：O157.5[理学—数学]