论文部分内容阅读
一个给定的图是否存在用r种颜色的正常Pk着色？称该问题为图的（κ，r）路色数问题。本文研究其算法复杂性，并得到以下结果：对于任意给定的κ，2≤κ≤∞，图的（κ，2）路色数问题及直径为2的图的（κ，3）路色数问题都是NP-完全的；对于任意给定的κ，2≤κ<∞，平面图的（κ，3）路色数问题也是NP-完全的。