Quantum graphs are an operator space generalization of classical graphs that have appeared in different branches of mathematics including operator systems theory, non-commutative topology and quantum information theory. In this talk, I will review the different perspectives to quantum graphs and introduce a chromatic number for quantum graphs using a non-local game with quantum inputs and classical outputs. I will then show that many spectral lower bounds for chromatic numbers in the classical case (such as Hoffman’s bound) also hold in the setting of quantum graphs. This is achieved using an algebraic formulation of quantum graph coloring and tools from linear algebra.