Independent Sets in Classes Related to Chair-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. MWIS is known to be NP-complete in general, but solvable in polynomial time in classes of S_(i,j,k)-free graphs, where S_(i,j,k) is 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.