- INSTANCE: Graph .
- SOLUTION:
A subset
such that the subgraph
is
*k*-colorable, i.e., there is a coloring for*G'*of cardinality at most*k*. - MEASURE:
Cardinality of the subgraph, i.e., .

*Good News:*Approximable within [176] and [367].*Bad News:*APX-complete for [393].*Comment:*Equivalent to MAXIMUM*K*-CUT for unweighted graphs. Admits a PTAS if and [39].