Deterministic quantum non-locality and graph colorings

One of the most fascinating consequences of quantum theory are non-local correlations: Two–possibly distant–parts of a system can have a behavior under measurements unexplainable by shared information. A manifestation thereof is so-called pseudo-telepathy: Tasks that can be performed by two parties who share a quantum state, whereas classically, communication would be necessary to always succeed. We show that pseudo-telepathy games can often be modeled by graphs: The classical strategy to win the game is a coloring of this graph with a given number of colors. We discuss these parallels and study the class of graphs corresponding to the first two-party pseudo-telepathy game, proposed by Brassard, Cleve, and Tapp in 1999. This leads to a proof that the game indeed has the desired property.