Speaker: Hieu Dinh	
Day:  Wednesday, 2/21/2006
Room: ITEB 336
Time: 2:00pm

Title: On Semidefinite Programming Relaxations for Graph Coloring and Vertex Cover

Paper
Moses Charikar, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete
Algorithms, (2002).

Abstract (from the paper)
We investigate the power of a strengthened SDP relaxation for graph coloring whose value is equal to a variant of the Lovasz v-function. We show families of graphs where the value of relaxation is 2 + \epsilon for any fixed epsilon > 0, yet the chromatic number is n^delta for some fix \delta > 0, which is a function of \epsilon.  This demonstrates the bound provided by the SDP is not strong enough to color a 3-colorable graph with n^O(1) colors

http://www.cse.uconn.edu/~akiayias/csets/