Independent Sets in (P4+ P4 ,Triangle)-Free Graphs

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs G and H, G+ H denotes the disjoint union of G and H. This manuscript shows that (i) WIS can be solved for (P4+ P4, Triangle)-free graphs in polynomial time, where a P4 is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every (P4+ P4, Triangle)-free graph G there is a family S of subsets of V(G) inducing (complete) bipartite subgraphs of G, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of G is contained in some member of S. These results seem to be harmonic with respect to other polynomial results for WIS on [subclasses of] certain Si,j,k-free graphs and to other structure results on [subclasses of] Triangle-free graphs.