Independent sets in extensions of 2K2-free graphs

The class of 2K2-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental property of 2K2-free graphs is that they contain polynomially many maximal independent sets. As a consequence, several important problems that are NP-hard in general graphs, such as 3-colorability, maximum weight independent set (WIS), minimum weight independent dominating set (WID), become polynomial-time solvable when restricted to the class of 2K2-free graphs. In the present paper, we extend 2K2-free graphs to larger classes with polynomial-time solvable WIS or WID. In particular, we show that WIS can be solved in polynomial time for (K2+K1,3)-free graphs and WID for (K2+K1,2)-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of 2K1,2-free graphs, which has been recently proven by Zverovich.