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).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.37--56
Liste complète des métadonnées

Littérature citée [51 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990588
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:38
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:41:34

Fichier

1747-7367-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990588, version 1

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. 〈hal-00990588〉

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

104