HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal.inria.fr/hal-00990588
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
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

File

1747-7367-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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. ⟨10.46298/dmtcs.579⟩. ⟨hal-00990588⟩

Share

Metrics

Record views

55

Files downloads

468