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.

Håstad'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- \varepsilon} for arbitrarily small constant \varepsilon > 0 unless NP=ZPP. In this paper, we aim at getting the best sub-constant value of \varepsilon in Håstad's result. We prove that clique size is inapproximable within a factor \frac{n}{{2(\log n)^{1 - \gamma } }} (corresponding to \varepsilon = \frac{1}{{(\log n)^\gamma }} for some constant \gamma > 0 unless NP \subseteq ZPTIME(2^{(\log n)^{0(1)} } ). This improves the previous best inapproximability factor of \frac{n}{{2^{0({{\log n} \mathord{\left/ {\vphantom {{\log n} {\sqrt {\log \log n} }}} \right. \kern-\nulldelimiterspace} {\sqrt {\log \log n} }}} }} (corresponding to \varepsilon = 0(\frac{1} {{\sqrt {\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- \varepsilon} for any constant \varepsilon > 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 \frac{n}{{2(\log n)^{1 - \gamma } }} for some constant \gamma > 0. The above two results 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 K\frac{1}{{25}}(\log k) colors. This improves a result of Fürer [11] that for arbitrarily small constant \varepsilon > 0, for sufficiently large constants k, it is hard to color a k-colorable graph with k^{3/2-\varepsilon} colors.