摘要
一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题．本文研究其算法复杂性，并得到以下结果：对于任意给定的ｋ，２≤ｋ≤∞，图的（ｋ，２）路色数问题及直径为２的图的（ｋ，３）路色数问题都是ＮＰ－完全的；对于任意给定的ｋ，２≤ｋ≤∞，平面图的（ｋ，３）路色数问题也是ＮＰ－完全的．
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.
出处
《数学研究》
CSCD
1995年第1期49-53,共5页
Journal of Mathematical Study
基金
国家自然科学基金
