直径为2的图的P_2路色问题  

P_2 Path Colouring Programme of Graphs with Diameter Two

作　　者：李瑾[1] 洪百会 

机构地区：[1]沈阳工业学院基础部,辽宁沈阳110045 [2]沈阳计算机技术研究设计院,辽宁沈阳110036

出　　处：《沈阳建筑工程学院学报（自然科学版）》2003年第1期75-77,共3页Journal of Shenyang Architectural and Civil Engineering University(Nature Science)

摘　　要：针对以r为参数的直径为 2的图的 (2 ,r)路色数的计算复杂性问题 ,从直径为 2的图及任意给定的整数r ≥ 3,图的 (2 ,r) 路色数问题是NP 完全的入手 ,给出直径为 2的 (2 ,2 )的路色图的一个好的刻划 ,并由此给出该问题一个多项式时间算法 ,从而解决了以r为参数的直径为 2的图的 (2 ,r)Focusing on the problem of the computational complexity for the (2, r ) path chromatic number of graphs with parameter r and beginning with the premise that for any fixed Integer 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 graphs with diameter 2 and a polynomial time algorithm, and hence solves the classification of the computational complexity for the (2, r ) path chromatic number problem of graphs with parameter r .

关 键 词：直径 P2路色问题 路色图 着色 路色数 计算复杂性 NP-完全 多项时间算法 

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