Improved hardness results for approximating the chromatic number

First, a simplified geometric proof is presented for the result of C. Lund and M. Yannakakis (1994) saying that for some ε>0 it is NP-hard to approximate the chromatic number of graphs with N vertices by a factor of N^ε. Then, more sophisticated techniques are employed to improve the exponent. A randomized twisting method allows us to completely pack a certain space with copies of a graph without much affecting the independence number. Together with the newest results of M. Bellare et al. (1995), on the number of amortized free bits, it is shown that for every ε>0 the chromatic number cannot be approximated by a factor of N^1/5-ε unless NP=ZPP. Finally, we get polynomial lower bounds in terms of χ. Unless NP=ZPP, the performance ratio of every polynomial time algorithm approximating the chromatic number of χ-colorable graphs (i.e., the chromatic number is at most χ) is at least χ^1/5-o(1) (where the o-notation is with respect to χ)