ECCC-Report TR05-039https://eccc.weizmann.ac.il/report/2005/039Comments and Revisions published for TR05-039en-usWed, 13 Apr 2005 21:42:24 +0300
Paper TR05-039
| Conditional Hardness for Approximate Coloring |
Irit Dinur,
Elchanan Mossel,
Oded Regev
https://eccc.weizmann.ac.il/report/2005/039We 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].
Wed, 13 Apr 2005 21:42:24 +0300https://eccc.weizmann.ac.il/report/2005/039