Feige, Uriel and Langberg, Michael and Schechtman, Gideon (2004) Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM Journal on Computing, 33 (6). pp. 13381368. ISSN 00975397. http://resolver.caltech.edu/CaltechAUTHORS:20111012111737057

PDF
 Published Version
See Usage Policy. 356Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111012111737057
Abstract
Karger, Motwani, and Sudan [J. ACM, 45 (1998), pp. 246265] introduced the notion of a vector coloring of a graph. In particular, they showed that every kcolorable graph is also vector kcolorable, and that for constant k, graphs that are vector kcolorable can be colored by roughly Δ^(1  2/k) colors. Here Δ is the maximum degree in the graph and is assumed to be of the order of n^5 for some 0 < δ < 1. Their results play a major role in the best approximation algorithms used for coloring and for maximum independent sets. We show that for every positive integer k there are graphs that are vector kcolorable but do not have independent sets significantly larger than n/Δ^(1 2/k) (and hence cannot be colored with significantly fewer than Δ^(12/k) colors). For k = O(log n/log log n) we show vector kcolorable graphs that do not have independent sets of size (log n)^c, for some constant c. This shows that the vector chromatic number does not approximate the chromatic number within factors better than n/polylogn. As part of our proof, we analyze "property testing" algorithms that distinguish between graphs that have an independent set of size n/k, and graphs that are "far" from having such an independent set. Our bounds on the sample size improve previous bounds of Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653750] for this problem.
Item Type:  Article  

Related URLs: 
 
Additional Information:  © 2004 Society for Industrial and Applied Mathematics. Received by the editors July 9, 2003; accepted for publication (in revised form) March 2, 2004; published electronically August 6, 2004. We would like to thank Luca Trevisan for his suggestion to analyze edge sampling. This author was supported in part by the Israel Science Foundation (grant 236/02). This author’s work was done while studying at the Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel 76100. The work of this author was supported in part by the Israel Science Foundation (grant 154/01).  
Funders: 
 
Subject Keywords:  semidefinite programming, chromatic number, independent set, approximation algorithms, property testing  
Classification Code:  AMS subject classifications: 68R05, 05C15, 90C22  
Record Number:  CaltechAUTHORS:20111012111737057  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20111012111737057  
Official Citation:  Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers Uriel Feige, Michael Langberg, and Gideon Schechtman SIAM J. Comput. 33, pp. 13381368  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  27189  
Collection:  CaltechAUTHORS  
Deposited By:  Ruth Sustaita  
Deposited On:  13 Oct 2011 14:52  
Last Modified:  26 Dec 2012 14:16 
Repository Staff Only: item control page