Motivated by a problem in quantum entanglement, we consider the quantum chromatic number of a graph. This turns out to be nicely related to other graph parameters. We will survey some known results and offer open questions as well.
No understanding of quantum physics is presumed on the part of the audience.
Parts of this are joint work with Godsil, and with Cameron, Montanaro, Severini and Winter.