Affordable Access

Deciding k-colorability of P5-free graphs in polynomial time

Springer Verlag
Publication Date
  • Qa76 Electronic Computers. Computer Science. Computer Software
  • Qa Mathematics
  • Computer Science


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.

There are no comments yet on this publication. Be the first to share your thoughts.