2020/03/19 by Mosca, Raffaele
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.08649
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 \cal 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 \cal S. These results seem to be harmonic with respect to other polynomial results for WIS on certain [subclasses of] Si,j,k-free graphs and to other structure results on [subclasses of] Triangle-free graphs.