TY - GEN
T1 - New approximation guarantee for chromatic number
AU - Arora, Sanjeev
AU - Chlamtac, Eden
AU - Charikar, Moses
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Chromatic number
KW - Graph coloring
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=33748105942&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748105942&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33748105942
SN - 1595931341
SN - 9781595931344
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 215
EP - 224
BT - STOC'06
T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06
Y2 - 21 May 2006 through 23 May 2006
ER -