Weighted independent sets in classes of P6-free graphs

International audienceThe Maximum Weight Independent Set (MWIS) problem on graphs with vertex weightsasks for a set of pairwise nonadjacent vertices of maximum total weight. The complexityof the MWIS problem for P6-free graphs, and for S1,2,2-free graphs are unknown. In thisnote, we give a proof for the solvability of the MWIS problem for (P6, S1,2,2, co-chair)-freegraphs in polynomial time, by analyzing the structure and the MWIS problem in varioussubclasses of (P6, S1,2,2, co-chair)-free graphs. These results extend some known results inthe literature