Some Results on Stable Sets for k-Colorable P6-Free Graphs and Generalizations
Raffaele Mosca
Abstract
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