Conditional hardness for approximate coloring

Irit Dinur, Elchanan Mossel, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 < Q. For q ≥ 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 '⋉ shaped' variant of his conjecture. We also prove that the problem ALMOST-3-COLORINGε is hard for any constant ε > 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].

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages344-353
Number of pages10
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/23/06

Keywords

  • Graph Coloring
  • Hardness of Approximation
  • Unique Games Conjecture

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Conditional hardness for approximate coloring'. Together they form a unique fingerprint.

  • Cite this

    Dinur, I., Mossel, E., & Regev, O. (2006). Conditional hardness for approximate coloring. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (pp. 344-353). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006). Association for Computing Machinery. https://doi.org/10.1145/1132516.1132567