Irit Dinur, Elchanan Mossel, Oded Regev

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 ...
more >>>