Non-local games originated in the 1960s as experiments that can demonstrate behaviors in quantum mechanics that cannot be replicated using classical mechanics alone. Since that time, these games have received considerable attention, partially due to the deep connections between them and other areas of mathematics, such as non-commutative geometry, functional analysis, combinatorics and computational complexity theory. In this talk, we will look at examples of non-local games that relate to graph theory, such as the coloring game, the homomorphism game, and the isomorphism game for graphs. We will see recent progress on these games towards separating some of the common models used in quantum information. We will also look at some of the major open problems in this area.
