Conditional hardness for approximate coloring

Irit Dinur, Elchanan Mossel, Oded Regev

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


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
Number of pages10
ISBN (Print)1595931341, 9781595931344
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
ISSN (Print)0737-8017


Other38th Annual ACM Symposium on Theory of Computing, STOC'06
Country/TerritoryUnited States
CitySeattle, WA


  • Graph Coloring
  • Hardness of Approximation
  • Unique Games Conjecture

ASJC Scopus subject areas

  • Software


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

Cite this