Independent sets of maximum weight in (\(p,q\))-colorable graphs. (Q1874371)

The authors consider \((p,q)\)-colorable graphs (their vertex sets can be partitioned into at most \(p\) cliques and \(q\) independent sets). In particular, \((0,2)\)-colorable graphs are bipartite, and \((1,1)\)-colorable are split graphs. For both of these classes, the problem of finding a maximum weight independent set is known to be solvable in polynomial time. In this note the authors give a complete classification of the family of \((p,q)\)-colorable graphs with respect to time complexity of this problem. Specifically, they show that the problem has a polynomial time solution in the class of \((p,q)\)-colorable graphs if and only if \(q \leq 2\) (assuming \(\mathcal{P} \neq \mathcal{NP}\)).