Equitable Partition of Graphs into Independent Sets and Cliques
A graph is (k, l) if its vertex set can be partitioned into k independent sets and l cliques. Deciding if a graph is (k, l) can be seen as a generalization of coloring, since deciding is a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable. A coloring is equitable if the cardinalities of the color classes differ by at most 1. In this paper, we generalize both the (k, l) and the equitable coloring problems, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and l cliques is solvable in polynomial time if max(k, l) 2, and NP complete otherwise.
Brandst¨adt, A. (1996). Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics, 152(1-3):47–54.
Brandst¨adt, A. (1998). Corrigendum. Discrete Math., 186:295.
Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity ofcom- puter computations, pages 85–103. Springer.