Stable sets in k-colorable P-5-free graphs
We show that, for fixed k, there is a polynomial-time algorithm that finds a maximum (or maximum-weight) stable set in any graph that belongs to the class of k-colorable P-5-free graphs, or, more generally. to the Class Of P5-free graphs that contain no clique of size k + 1. This is based on the following structural result: every connected k-colorable P5-free graph has a vertex whose non-neighbors induce a (k - 1)-colorable subgraph. (C) 2009 Elsevier B.V. All rights reserved.
graph algorithm stability