Conditional hardness for approximate coloring

We study the APPROXCOLORING q(Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q 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 a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε.Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

Authors

• Irit Dinur
• Elchanan Mossel
• Oded Regev 0001

Keywords

• graph coloring
• hardness of approximation
• unique games conjecture