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

*Good News:*As easy to approximate as MAXIMUM INDEPENDENT SET for (finding*k*independent sets) [221].*Bad News:*As hard to approximate as MAXIMUM INDEPENDENT SET for [389].*Comment:*Transformation from MAXIMUM INDEPENDENT SET. Equivalent to MAXIMUM INDEPENDENT SET for*k=1*. Admits a PTAS for planar graphs [53]. Admits a PTAS for `-near-planar' instances for any [263]. The case of degrees bounded by , for is approximable within [222] and APX-complete.