More Tales of Hoffman: bounds for the vector chromatic number of a graph

Abstract

Let $\chi (G)$ denote the chromatic number of a graph and ${\chi }_v(G)$ denote the vector chromatic number. For all graphs ${\chi }_v(G)\le \chi (G)$ and for some graphs ${\chi }_v(G)\ll \chi (G)$. Galtman proved that Hoffman's well-known lower bound for $\chi (G)$ is in fact a lower bound for ${\chi }_v(G)$. We prove that two more spectral lower bounds for $\chi (G)$ are also lower bounds for ${\chi }_v(G)$. We then use one of these bounds to derive a new characterization of ${\chi }_v(G)$.

added alternative proof of Lima bound; added reference to Galtman; authors welcome comments