DIMACS TR: 2006-15
Polynomial-time algorithm for vertex k-colorability of P5-free graphs
Authors: Marcin Kaminski and Vadim Lozin
We give the first polynomial-time algorithm for coloring vertices of P5-free graphs with k colors. This settles an open problem and generalizes several previously known results.
Paper Available at:
DIMACS Home Page