New Approximation Guarantee for Chromatic Number

Eden Chlamtac
Princeton University

Friday, November 10th, 2006, 3:30 pm
Wean Hall 7220

Abstract

We describe an algorithm which colors any 3-colorable graph using O(n^0.2074) colors, thus improving the algorithms of Karger, Motwani and Sudan, and Blum and Karger from almost a decade ago. The previous best known algorithm used O(n^{3/14}) colors. We build on these results, which combined semidefinite programming (SDP) relaxations (specifically, vector chromatic number) with some combinatorial techniques.

We demonstrate a better relation between vector chromatic number and true chromatic number. While this already gives some improvement, we obtain our best result by working with stronger SDP relaxations (e.g. by adding "odd-cycle constraints"). Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao and Vazirani.

This is joint work with Sanjeev Arora and Moses Charikar.