In this talk, we will explore the interaction between operator algebras and quantum information theory through a discussion on quantum graphs. Quantum graphs are an operator generalization of classical graphs that have appeared in different branches of mathematics including operator algebras, non-commutative topology, operator systems theory and quantum information theory. I will present an overview of the theory of quantum graphs and discuss the connections between different perspectives using operator algebraic methods. We will then investigate a coloring problem for quantum graphs using a quantum-input classical-output nonlocal game. Using this framework, we show that every quantum graph has a finite quantum coloring, but not necessarily finite classical coloring. We will develop a combinatorial characterization of quantum graph coloring using the winning strategies of this game and obtain various lower bounds for the chromatic numbers of quantum graphs. This is based on joint work with Michael Brannan and Samuel Harris.