- INSTANCE: Graph .
- SOLUTION:
A complete coloring of
*G*, i.e., a partition of*V*into disjoint sets such that each is an independent set for*G*and such that, for each pair of distinct sets , , is*not*an independent set. - MEASURE:
Cardinality of the complete coloring, i.e., the number of disjoint
independent sets .

*Good News:*Approximable within [100].*Comment:*Approximable within for graphs of girth (length of shortest cycle) at least 6 [100].*Garey and Johnson:*GT5