Improved Hardness
of Approximating Chromatic Number
Sangxia Huang
We prove that for sufficiently large \(K\), it is NP-hard to
color \(K\)-colorable graphs with less than \(2^{\Omega(K^{1/3})}\) colors.
This improves the previous result of \(K\) versus \(K^{\frac{1}{25} \log K}\) in Khot [21].