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].