Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring

In this paper, we present improved inapproximability results for three problems : the problem of finding the maximum clique size in a graph, the problem of finding the chromatic number of a graph, and the problem of coloring a graph with a small chromatic number with a small number of colors. Hastad's celebrated result [13] shows that the maximum clique size in a graph with n vertices is inapproximable in polynomial time within a factor n(1-epsilon) for arbitrarily small constant epsilon > 0 unless NP=ZPP. In this paper, we aim at getting the best subconstant value of epsilon in Hastad's result. We prove that clique size is inapproximable within a factor n/2((log n)1 - gamma) (corresponding to epsilon = 1/(log n)(gamma) ) for some constant gamma > 0 unless NP subset of or equal to ZPTIME(2((log n)O(1))). This improves the previous best inapproximability factor of n/2(O(log n/root log log n)) (corresponding to epsilon = O(1/root log log n)) due to Engebretsen and Holmerin [7]. A similar result is obtained for the problem of approximating chromatic number of a graph. Feige and Kilian [10] prove that chromatic number is hard to approximate within factor n(1-epsilon) for any constant epsilon > 0 unless NP=ZPP. We use some of their techniques to give a much simpler proof of the same result and also improve the hardness factor to - n for some constant gamma > 0. The above two results n/2(log n)(1 - gamma) are obtained by constructing a new Hadamard code based PCP inner verifier. We also present a new hardness result for approximate graph coloring. We show that for all sufficiently large constants k, it is NP-hard to color a k-colorable graph with k1/25((log k)) colors. This improves a result of Furer [11] that for arbitrarily small constant epsilon > 0, for sufficiently large constants k, it is hard to color a k-colorable graph with k(3/2-epsilon) colors.