Clique and anticlique partitions of graphs Original Research Article

In the paper we prove that, for a fixed k, the problem of deciding whether a graph admits a partition of its vertex set into k-element cliques or anticliques (i.e. independent sets) is polynomial.