### Some Results on Stable Sets for k-Colorable P_{6}-Free Graphs and Generalizations

*Raffaele Mosca*

#### Abstract

This article deals with the Maximum Weight Stable Set
(

*MWS*) problem (and some other related NP-hard problems) and the class of P_{6}-free graphs. The complexity status of MWS is open for P_{6}-free graphs and is open even for P_{5}-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P_{5}-free: in particular, MWS can be solved for k-colorable P_{5}-free graphs in polynomial time for every k (depending on k) and more generally for (P_{5},K_{p})-free graphs (depending on p), which is a useful result since for every graph G one can easily compute a k-coloring of G, with k not necessarily minimum. This article studies the MWS problem for k-colorable P_{6}-free graphs and more generally for (P_{6},K_{p})-free graphs. Though we were not able to define a polynomial time algorithm for this problem for every k, this article introduces: (i) some structure properties of P_{6}-free graphs with respect to stable sets, (ii) two reductions for MWS on (P_{6},K_{p})-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P_{6}-free, for 4-colorable P_{6}-free, and for (P_{6},K_{4})-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P_{6},F)-free graphs in polynomial time where F is any four vertex graph).Full Text: PDF PostScript