Next:
MAXIMUM SUBFOREST
Up:
Subgraphs and Supergraphs
Previous:
MINIMUM EDGE DELETION K-PARTITION
 
Index
M
AXIMUM
K
-C
OLORABLE
S
UBGRAPH
I
NSTANCE:
Graph
.
S
OLUTION:
A subset
such that the subgraph
is
k
-colorable, i.e., there is a coloring for
G'
of cardinality at most
k
.
M
EASURE:
Cardinality of the subgraph, i.e.,
.
Good News:
Approximable within
[
176
] and [
367
].
Bad News:
A
PX
-complete for
[
393
].
Comment:
Equivalent to M
AXIMUM
K
-C
UT
for unweighted graphs. Admits a PTAS if
and
[
39
].
Viggo Kann
2000-03-20