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

- Authors
- Publisher
- Springer Verlag
- Publication Date
- Keywords
- Disciplines

## Abstract

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.