Next: MINIMUM EDGE COLORING
Up: Covering and Partitioning
Previous: MINIMUM GRAPH COLORING
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A complete coloring of G, i.e., a partition of V into disjoint sets
such that each Vi is an independent set for G
and such that, for each pair of distinct sets Vi, Vj,
is not an independent set.
- MEASURE:
Cardinality of the complete coloring, i.e., the number of disjoint
independent sets Vi.
- Good News:
Approximable within
[92].
- Comment:
Approximable within
for graphs of girth (length of shortest
cycle) at least 6 [92].
- Garey and Johnson: GT5
Viggo Kann
1999-04-22