Next: MAXIMUM SUBFOREST Up: Subgraphs and Supergraphs Previous: MINIMUM EDGE DELETION K-PARTITION Index

### MAXIMUM K-COLORABLE SUBGRAPH

- INSTANCE: Graph .

- SOLUTION: A subset such that the subgraph is k-colorable, i.e., there is a coloring for G' of cardinality at most k.

- MEASURE: Cardinality of the subgraph, i.e., |E'|.

- Good News: Approximable within [164] and [347].

- Bad News: APX-complete for [371].

- Comment: Equivalent to MAXIMUM K-CUT for unweighted graphs. Admits a PTAS if and k=o(|V|) [37].