On semidefinite programming relaxations for graph coloring and vertex cover
Moses Charikar · 2002
Abstract We investigate the power of a strengthened SDP relaxation for graph coloring whose value is equal to a variant of the Lov'asz #-function. We show families of graphs where the value of the relaxation is 2 + ffl for any fixed ffl? 0, yet the chromatic number is n ffi for some fixed ffi? 0, which is a function of ffl. This demonstrates the bound provided by the SDP is not strong enough to color a 3-colorable graph with n o(1) colors. Kleinberg and Goemans considered an SDP relaxation for vertex cover whose value is n \\Gamma #1=2 (#1=2 being the variant of the #-function introduced by Schrijver). They asked whether this is within a ratio of 2 \\Gamma ffl of the optimal vertex cover for any ffl? 0. Our construction answers this question negatively. 1 Introduction Consider the following question in combinatorial geometry: Given a set U of points on the unit sphere, consider the graph GU on these points, obtained by connecting points whose distance is equal to the diameter dU of the point set. As the diameter dU approaches 2, how large can the chromatic number O/(GU) be?