Improved Hardness of Approximating Chromatic Number

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^{1/25 * logK} by Khot.