TY - JOUR
T1 - Graphs with tiny vector chromatic numbers and huge chromatic numbers
AU - Feige, Uriel
AU - Langberg, Michael
AU - Schechtman, Gideon
PY - 2002
Y1 - 2002
N2 - Karger, Motwani and Sudan (JACM 1998) introduced the notion of a vector coloring of a graph. In particular they show that every k-colorable graph is also vector k-colorable, and that for constant k, graphs that are vector k-colorable can be colored by roughly Δ1-2/k colors. Here Δ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set. We show that for every positive integer k there are graphs that are vector k-colorable but do not have independent sets significantly larger than n/Δ1-2/k (and hence cannot be colored with significantly less that Δ1-2/k colors). For k = O(log n/log log n) we show vector k-colorable 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 (JACM 1998) for this problem.
AB - Karger, Motwani and Sudan (JACM 1998) introduced the notion of a vector coloring of a graph. In particular they show that every k-colorable graph is also vector k-colorable, and that for constant k, graphs that are vector k-colorable can be colored by roughly Δ1-2/k colors. Here Δ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set. We show that for every positive integer k there are graphs that are vector k-colorable but do not have independent sets significantly larger than n/Δ1-2/k (and hence cannot be colored with significantly less that Δ1-2/k colors). For k = O(log n/log log n) we show vector k-colorable 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 (JACM 1998) for this problem.
UR - http://www.scopus.com/inward/record.url?scp=0036953749&partnerID=8YFLogxK
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.conferencearticle???
AN - SCOPUS:0036953749
SN - 0272-5428
SP - 283
EP - 292
JO - Annual Symposium on Foundations of Computer Science - Proceedings
JF - Annual Symposium on Foundations of Computer Science - Proceedings
T2 - The 34rd Annual IEEE Symposium on Foundations of Computer Science
Y2 - 16 November 2002 through 19 November 2002
ER -