MINIMUM GRAPH COLORING

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A coloring of G, i.e., a partition of V into disjoint sets $V_1,V_2,\ldots,V_k$ such that each $V_i$ is an independent set for G.
• MEASURE: Cardinality of the coloring, i.e., the number of disjoint independent sets $V_i$.

  
  

• Good News: Approximable within $O\left(\vert V\vert \displaystyle\frac{(\log\log\vert V\vert)^2}{(\log\vert V\vert)^3}\right)$ [219].
• Bad News: Not approximable within $\vert V\vert^{1/7-\varepsilon }$ for any $\varepsilon >0$ [68].
• Comment: Also called Minimum Chromatic Number. Not approximable within $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$, unless ZPP=NP [156]. If the graph is 3-colorable, the problem is approximable within $O(\vert V\vert^{3/14}\log^{O(1)}\vert V\vert)$ [85], but not approximable within $5/3-\varepsilon$ [303]. If the graph is k-colorable the problem is approximable within $O(\vert V\vert^{1-3/(k+1)}\log\vert V\vert)$ [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 $O(\vert V\vert (\log\log \vert V\vert/\log \vert V\vert)^2)$ in hypergraphs [340], and is hard to approximate within $\vert V\vert^{1-\varepsilon }$ unless NP=ZPP [257,340]. MINIMUM COLORING WITH DEFECT D, the variation where the color classes $V_i$ may induce graphs of degree at most d, is not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [123]. MINIMUM FRACTIONAL CHROMATIC NUMBER, the linear programming relaxation in which the independent sets $V_1,V_2,\ldots,V_k$ do not need to be disjoint, and in the solution every independent set $V_i$ is assigned a nonnegative value $\lambda_i$ such that for each vertex $v\in V$ the sum of the values assigned to the independent sets containing v is at most 1, and the measure is the sum $\sum\lambda_i$, is always within $\log$ 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. $\vert V\vert-k$, is to be maximized, is approximable within 360/289 [140].
• Garey and Johnson: GT4