直径为2的图的P＿2路色问题

P_2PATH COLORKING PTOBLEM OF GTAPHS WITH DIAMETER TWO

一个给定的图是否存在用ｒ种颜色的正常Ｐ＿ｋ着色？称该问题为图的（ｋ，ｒ）路色数问题。已知对于直径为２的图及任意给定的整数ｒ≥３，图的（２，ｒ）路色数问题是ＮＰ－完全的。本文给出直径为２的（２，２）路色图的一个好的刻划，并由此给出该问题的一个多项式时间算法，从而解决了以ｒ为参数的直径为２的图的（２，ｒ）路色数问题的计算复杂性分类。

Is there a normal P_k coloring for a given graph with r colors?This problem is calledthe(k,r)path chrematic number problem of graphs. It has been known that for any fixedinteger r≥3 the(2,r)path chromatic number problem for graphs with diameter 2 is NP-complete, This paper gives out a good characterization for(2,2)path chromatic graphswith diameter 2 and a polynomial time algorithm,hence solves the classification of thecomputational complexity for the(2,r)path chromatic number problem of graphs with pa-rameter r.