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.