Independent sets in extensions of 2K2-free graphs

The class of 2K(2)-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 2K(2)-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 2K(2)-free graphs. In the present paper, we extend 2K(2)-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 (K-2 + K-1,K-3)-free graphs and WID for (K-2 + K-1.2)-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of 2K(1.2)-free graphs, which has been recently proven by Zverovich. (C) 2004 Elsevier B.V. All rights reserved.