Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

Some Results on Stable Sets for k-Colorable P6-Free Graphs and Generalizations

Raffaele Mosca


This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P6-free graphs. The complexity status of MWS is open for P6-free graphs and is open even for P5-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P5-free: in particular, MWS can be solved for k-colorable P5-free graphs in polynomial time for every k (depending on k) and more generally for (P5,Kp)-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 P6-free graphs and more generally for (P6,Kp)-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 P6-free graphs with respect to stable sets, (ii) two reductions for MWS on (P6,Kp)-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P6-free, for 4-colorable P6-free, and for (P6,K4)-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P6,F)-free graphs in polynomial time where F is any four vertex graph).

Full Text: PDF PostScript