Conditional Hardness for Approximate Coloring
<|reference_start|>Conditional Hardness for Approximate Coloring: We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. 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 `fish shaped' variant of his conjecture.   We also prove that the problem almost coloring 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 a $\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].<|reference_end|>
@article{dinur2005conditional,
    title={Conditional Hardness for Approximate Coloring},
    author={Irit Dinur and Elchanan Mossel and Oded Regev},
    journal={arXiv preprint arXiv:cs/0504062},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0504062},
    primaryClass={cs.CC math.PR}
}