Weighted independent sets in classes of P6 P 6 -free graphs
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for P6 P 6 -free graphs, and for S1,2,2 S 1 , 2 , 2 -free graphs are unknown. In this note, we give a proof for the solvability of the MWIS problem for (P6 P 6 , S1,2,2 S 1 , 2 , 2 , co-chair)-free graphs in polynomial time, by analyzing the structure and the MWIS problem in various subclasses of (P6 P 6 , S1,2,2 S 1 , 2 , 2 , co-chair)-free graphs. These results extend some known results in the literature.
weighted independent set graph algorithms clique separator modular decomposition p6 p 6 -free graph p6 p 6 p6 p 6 p 6 claw-free graph