Problem: Clique cover

Definition:
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI