New approximation guarantee for chromatic number

Sanjeev Arora, Eden Chlamtac, Moses Charikar

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

47 Scopus citations

Abstract

We describe how to color every 3-colorable graph with O(n 0.2111) colors, thus improving an algorithm of Blum and Karger from almost a decade ago. Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao, and Vazirani on SPARSEST CUT, and these ideas show promise of leading to further improvements.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
Pages215-224
Number of pages10
StatePublished - Sep 5 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

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Chromatic number
  • Graph coloring
  • Semidefinite programming

Fingerprint Dive into the research topics of 'New approximation guarantee for chromatic number'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Chlamtac, E., & Charikar, M. (2006). New approximation guarantee for chromatic number. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (pp. 215-224). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006).