Graphs with tiny vector chromatic numbers and huge chromatic numbers

Karger Motwani and Sudan (1998) introduced the notion of a vector coloring of a graph. In particular they show that every k-colorable graph is also vector k-...