Next: MINIMUM COLOR SUM
Up: Covering and Partitioning
Previous: MINIMUM INDEPENDENT DOMINATING SET
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A coloring of G, i.e., a partition of V into disjoint sets
such that each
is an independent set for G.
- MEASURE:
Cardinality of the coloring, i.e., the number of disjoint independent sets
.
- Good News:
Approximable within
[219].
- Bad News:
Not approximable within
for any
[68].
- Comment:
Also called Minimum Chromatic Number.
Not approximable within
for any
,
unless ZPP=NP [156].
If the graph is 3-colorable, the problem is approximable within
[85],
but not approximable within
[303].
If the graph is k-colorable the problem is approximable within
[290].
Approximable with an absolute error guarantee of 1 on planar graphs
by the Four Color Theorem.
Approximable within 3 but not within 1.33 for unit disk graphs
[370].
Approximable within 1+1/e + o(1) on circular arc graphs
[343].
Approximable within
in hypergraphs
[340], and is hard to approximate within
unless NP=ZPP [257,340].
MINIMUM COLORING WITH DEFECT D, the variation where the color
classes
may induce graphs of degree at most d, is not approximable
within
for some
[123].
MINIMUM FRACTIONAL
CHROMATIC NUMBER, the linear programming relaxation in
which the independent sets
do not need to be
disjoint, and in the solution every independent set
is assigned a
nonnegative value
such that for each vertex
the
sum of the values assigned to the independent sets containing v is
at most 1, and the measure is the sum
,
is always within
factor from the chromatic number
thus the same bad news apply [365].
The complementary maximization problem, where the number of ``not needed
colors'', i.e.
,
is to be maximized, is approximable
within 360/289 [140].
- Garey and Johnson: GT4
Next: MINIMUM COLOR SUM
Up: Covering and Partitioning
Previous: MINIMUM INDEPENDENT DOMINATING SET
  Index
Viggo Kann
2000-03-20