Improved Hardness of Approximating Chromatic Number

Sangxia Huang

We prove that for sufficiently large , it is NP-hard to color -colorable graphs with less than colors. This improves the previous result of versus by Khot.

[PDF]