such that the induced subgraph
k-colorable, i.e., there is a coloring for G' of cardinality at most k.
Cardinality of the vertex set of the induced subgraph, i.e., .
As easy to approximate as MAXIMUM INDEPENDENT SET for
As hard to approximate as MAXIMUM INDEPENDENT SET for
Transformation from MAXIMUM INDEPENDENT SET.
Equivalent to MAXIMUM INDEPENDENT SET for k=1.
Admits a PTAS for planar graphs .
Admits a PTAS for `-near-planar' instances for any
The case of degrees bounded by ,