The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. MWIS is known to be $NP$-complete in general, even under various restrictions. Let $S_{ i,j,k}$ be the graph consisting of three induced paths of lengths $i, j, k$ with a common initial vertex. The complexity of the MWIS problem for $S_{ 1, 2, 2}$-free graphs, and for $S_{ 1, 1, 3}$-free graphs are open. In this paper, we show that the MWIS problem can solved in polynomial time for ($S_{ 1, 2, 2}$, $S_{ 1, 1, 3}$, co-chair)-free graphs, by analyzing the structure of the subclasses of this class of graphs. This extends some known results in the literature.
Categories: cs.DM math.CO