### 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 language | English (US) |
---|---|

Title of host publication | STOC'06 |

Subtitle of host publication | Proceedings of the 38th Annual ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 344-353 |

Number of pages | 10 |

ISBN (Print) | 1595931341, 9781595931344 |

DOIs | |

State | Published - 2006 |

Event | 38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 2006 |

ISSN (Print) | 0737-8017 |

### Other

Other | 38th Annual ACM Symposium on Theory of Computing, STOC'06 |
---|---|

Country | United States |

City | Seattle, WA |

Period | 5/21/06 → 5/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

*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