2006-15: Polynomial-time algorithm for vertex k-colorability of P5-free graphs

DIMACS TR: 2006-15

Polynomial-time algorithm for vertex k-colorability of P5-free graphs

Authors: Marcin Kaminski and Vadim Lozin

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-15.ps.gz

DIMACS Home Page