Next: MAXIMUM ACHROMATIC NUMBER Up: Covering and Partitioning Previous: MINIMUM INDEPENDENT DOMINATING SET Index

### MINIMUM GRAPH COLORING

- INSTANCE: Graph .

- SOLUTION: A coloring of G, i.e., a partition of V into disjoint sets such that each Vi is an independent set for G.

- MEASURE: Cardinality of the coloring, i.e., the number of disjoint independent sets Vi.

- Good News: Approximable within [206].

- Bad News: Not approximable within for any [63].

- Comment: Also called Minimum Chromatic Number. Not approximable within for any , unless co-RP=NP [144]. If the graph is 3-colorable the problem is approximable within [80] and [347], but not approximable within 5/3 [288]. If the graph is k-colorable the problem is approximable within [275]. Approximable with an absolute error guarantee of 1 on planar graphs by the Four Color Theorem, see e.g. [245]. Approximable within 3 but not within 1.33 for unit disk graphs [350]. Approximable within 1+1/e + o(1) on circular arc graphs [327].

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

- Garey and Johnson: GT4

Next: MAXIMUM ACHROMATIC NUMBER Up: Covering and Partitioning Previous: MINIMUM INDEPENDENT DOMINATING SET Index