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

摘要

针对以r为参数的直径为 2的图的 (2 ,r)路色数的计算复杂性问题 ,从直径为 2的图及任意给定的整数r ≥ 3,图的 (2 ,r) 路色数问题是NP 完全的入手 ,给出直径为 2的 (2 ,2 )的路色图的一个好的刻划 ,并由此给出该问题一个多项式时间算法 ,从而解决了以r为参数的直径为 2的图的 (2 ,r)