<i>Some Results on Stable Sets for k</i>-<i>Colorable P</i>₆-<i>Free Graphs and Generalizations</i>

作     者：Mosca, Raffaele 

作者机构：Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy 

出 版 物：《DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE》 (Discrete Math. Theor. Comput. Sci.)

年 卷 期：2012年第14卷第2期

页      面：37-56页

核心收录：

主　　题：Maximum Weight stable Set problem P6-free graphs polynomial algorithms 

摘      要：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).