Deciding k-Colorability of P (5)-Free Graphs in Polynomial Time

作者：Hoang Chinh T^*; Kaminski Marcin; Lozin Vadim; Sawada Joe; Shu Xiao

来源：Algorithmica, 2010, 57(1): 74-81.

DOI：10.1007/s00453-008-9197-8

• Graph coloring
• Dominating clique
• Polynomial-time algorithm
• P(5)-free graph

The problem of computing the chromatic number of a P (5)-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P (5)-free graph admits a k-coloring, and finding one, if it does.

• 出版日期2010-5