- INSTANCE: Graph .
- SOLUTION:
A clique partition for
*G*, i.e., a partition of*V*into disjoint subsets such that, for , the subgraph induced by is a complete graph. - MEASURE:
Cardinality of the clique partition, i.e., the number of disjoint subsets
.

*Good News:*Equivalent to MINIMUM GRAPH COLORING [396]. See results theirein.*Garey and Johnson:*GT15