Next: MINIMUM EQUIVALENT DIGRAPH Up: Subgraphs and Supergraphs Previous: MINIMUM EDGE 2-SPANNER Index

### MAXIMUM K-COLORABLE INDUCED SUBGRAPH

- 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., |V'|.

- Good News: As easy to approximate as MAXIMUM INDEPENDENT SET for (finding k independent sets) [208].

- Bad News: As hard to approximate as MAXIMUM INDEPENDENT SET for [368].

- Comment: Transformation from MAXIMUM INDEPENDENT SET. Equivalent to MAXIMUM INDEPENDENT SET for k=1. Admits a PTAS for planar graphs [50]. Admits a PTAS for `-near-planar' instances for any [248]. The case of degrees bounded by , for is approximable within (B/k + 1)/2 [209] and APX-complete.