GT5 M INIMUM G RAPH C OLORING

       
• I NSTANCE : Graph .
• S OLUTION : A coloring of G , i.e., a partition of V into disjoint sets such that each is an independent set for G .
• M EASURE : Cardinality of the coloring, i.e., the number of disjoint independent sets .

• Good News: Approximable within [ 148 ].
• Bad News: Not approximable within for any [ 40 ].
• Comment: Also called Minimum Chromatic Number .     Not approximable within for any , unless co-RP=NP [ 105 ]. If the graph is 3-colorable the problem is approximable within [ 207 ] and [ 265 ], but it is not approximable within 5/3 [ 215 ]. If the graph is k -colorable the problem is approximable within [ 207 ]. Approximable with an absolute error guarantee of 1 on planar graphs [see e.g. [ 177 ]].     Approximable within 3 but not within 1.33 for unit disk graphs [ 268 ].     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 [ 83 ].

  M INIMUM F RACTIONAL C HROMATIC N UMBER , 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 not approximable within for some constant c [ 264 ].  

  The complementary maximization problem, where the number of ``not needed colors'', i.e. |V|-k , is to be maximized, is approximable within 4/3 [ 153 ]. The constrained variation in which the input is extended with a positive integer k , a vertex and a subset S of V , and the problem is to find the k -coloring that colors the largest number of vertices from S in the same way as , is not approximable within for some [ 352 ].

• Garey and Johnson: GT4