GT34 M AXIMUM K -C OLORABLE I NDUCED S UBGRAPH

       
• I NSTANCE : Graph .
• S OLUTION : A subset such that the induced subgraph is k -colorable, i.e., there is a coloring for G' of cardinality at most k .
• M EASURE : Cardinality of the vertex set of the induced subgraph, i.e., |V'| .

• Good News: As easy to approximate as M AXIMUM I NDEPENDENT S ET for (finding k independent sets) [ 150 ].
• Bad News: As hard to approximate as M AXIMUM I NDEPENDENT S ET for [ 281 ].
• Comment: Transformation from M AXIMUM I NDEPENDENT S ET . Equivalent to M AXIMUM I NDEPENDENT S ET for k=1 . Admits a PTAS for ` -near-planar' instances for any [ 180 ]. Variation in which the degree of G is bounded by a constant B is approximable within (B/k + 1)/2 [ 151 ] and A PX -complete.