We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness result on a certain `alpha-
shaped' variant of his conjecture.

We also prove that the problem almost-approximate-3-coloring(eps) is hard for any constant eps>0, assuming Khot's
Unique Games conjecture. This is the problem of
deciding for a given graph, between the case where
one can 3-color all but an \eps fraction of the vertices without
monochromatic edges, and the case where the graph contains no
independent set of relative size at least \eps.

Our result is based on bounding various generalized noise-stability
quantities using the invariance principle of Mossel et al [MOO'05].