Abstract
The quantum chromatic number, χ_q(G), of a graph G was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of χ_q(G) to prove that many spectral lower bounds for the chromatic number, χ(G), are also lower bounds for χ_q(G). This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.