TY - JOUR

T1 - Graphs with tiny vector chromatic numbers and huge chromatic numbers

AU - Feige, Uriel

AU - Langberg, Michael

AU - Schechtman, Gideon

N1 - Funding Information:
This paper was supported by Konkuk University in 2000.

PY - 2004

Y1 - 2004

N2 - Karger, Motwani, and Sudan [J. ACM, 45 (1998), pp. 246-265] introduced the notion of a vector coloring of a graph. In particular, they showed 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 A is the maximum degree in the graph and is assumed to be of the order of n 2 for some 0 < 6 < 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 k-colorable but do not have independent sets significantly larger than n/Δ 1-2/k (and hence cannot be colored with significantly fewer than Δ 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 (logn) 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. 653-750] for this problem.

AB - Karger, Motwani, and Sudan [J. ACM, 45 (1998), pp. 246-265] introduced the notion of a vector coloring of a graph. In particular, they showed 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 A is the maximum degree in the graph and is assumed to be of the order of n 2 for some 0 < 6 < 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 k-colorable but do not have independent sets significantly larger than n/Δ 1-2/k (and hence cannot be colored with significantly fewer than Δ 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 (logn) 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. 653-750] for this problem.

KW - Approximation algorithms

KW - Chromatic number

KW - Independent set

KW - Property testing

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=11144336716&partnerID=8YFLogxK

U2 - 10.1137/S0097539703431391

DO - 10.1137/S0097539703431391

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:11144336716

SN - 0097-5397

VL - 33

SP - 1338

EP - 1368

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -