Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers

DOI10.1137/S0097539703431391zbMath1105.68088MaRDI QIDQ4651517

Michael Langberg, Gideon Schechtman, Uriel Feige

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

semidefinite programmingindependent setchromatic numberapproximation algorithmsproperty testing

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Constructing uniquely realizable graphs ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Unnamed Item ⋮ New Tools for Graph Coloring ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ More tales of Hoffman: bounds for the vector chromatic number of a graph