On the hardness of approximating the chromatic number (Q5932643)

The hardness of approximating the chromatic number when the input graph is \(k\)-colorable for some fixed \(k\geq 3\) is studied in this paper. The main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. An immediate corollary is that it is NP-hard to color a \(k\)-chromatic graph with at most \(k+2\lfloor k/3\rfloor\)-colors. Also, simple proofs of two results of \textit{C. Lund} and \textit{M. Yannakakis} [J. Assoc. Comput. Mach. 41, 960-981 (1994; Zbl 0814.68064)] are given. The first result shows that it is NP-hard to approximate the chromatic number to within \(n^{\varepsilon}\) for some fixed \(\varepsilon >0\). This hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant \(h\), there exists an integer \(k_h\), such that it is NP-hard to decide whether a given graph \(G\) is \(k_h\)-chromatic or any coloring of \(G\) requires \(h-k_h\) colors.