Deciding k-Colorability of P (5)-Free Graphs in Polynomial Time
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.
polynomial-time algorithm graph coloring dominating clique p(5)-free graph