Next: MAXIMUM SUBFOREST
Up: Subgraphs and Supergraphs
Previous: MINIMUM EDGE DELETION K-PARTITION
  Index
- 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].
Viggo Kann
1999-04-22