Eden Chlamtac
Senior Academic
New approximation guarantee for chromatic number
We describe how to color every 3-colorable graph with O(n0.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.
| Publication language | English |
| Pages | 215-224 |
| Publication status | Published - 01.01.2006 |
Keywords
Approximation algorithms
Chromatic number
Graph coloring
Semidefinite programming
ASJC Scopus subject areas
Software
