# Improved Hardness of Approximating Chromatic Number

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