TY - GEN

T1 - New approximation guarantee for chromatic number

AU - Arora, Sanjeev

AU - Chlamtac, Eden

AU - Charikar, Moses

PY - 2006/9/5

Y1 - 2006/9/5

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 -