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

P_2PATH COLORKING PTOBLEM OF GTAPHS WITH DIAMETER TWO

作　　者：原晋江[1] 康丽英[1] 

机构地区：[1]郑州大学,石家庄铁道学院

出　　处：《数学杂志》1995年第4期401-404,共4页Journal of Mathematics

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

关 键 词：图 着色 路色数 直径 平面图 

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