Independent Sets in Classes Related to Chair/Fork-free Graphs

Abstract

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.

arXiv admin note: text overlap with arXiv:1504.05401