[206].
Approximable within
in hypergraphs
[324], and is hard to approximate within
unless NP = ZPP [240,324].
MINIMUM COLORING WITH DEFECT D, the variation where the color
classes Vi may induce graphs of degree at most d, is not approximable
within
for some
[115].
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 Vi 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 [346].
The complementary maximization problem, where the number of ``not needed colors'', i.e. |V|-k, is to be maximized, is approximable within 6/5 [130].
[452].