Skip to Main content Skip to Navigation
Journal articles

Some results on stable sets for k-colorable P₆-free graphs and generalizations

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).
Document type :
Journal articles
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:27:38 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:41:34 PM


Files produced by the author(s)


  • HAL Id : hal-00990588, version 1



Raffaele Mosca. Some results on stable sets for k-colorable P₆-free graphs and generalizations. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.37--56. ⟨hal-00990588⟩



Record views


Files downloads