In this talk I will give a brief introduction to the theory of quantum graphs (a.k.a. noncommutative graphs). After going over the basic theory and motivations, I will explain how one can generalize the classical coloring problem for graphs to our quantum setting. I will highlight how the quantum coloring problem serves as a natural motivation for the recently developed theory of quantum non local games and quantum no-signalling correlations by Todorov and Turowska. I will also explain how quantum colorings give rise to new and interesting examples of non-amenable II$_1$-factors (which are not yet known to be Connes embeddable).

This is based on joint works with Priyanga Ganesan, Li Gao, Samuel Harris, John Weeks, Ivan Todorov, and Lyudmila Turowska.