## Relaxations of Graph Isomorphism

We introduce a two player non-local game based on graph isomorphisms. The input for the game is two graphs X and Y, and players attempt to convince a referee that there exists an isomorphism between X and Y. Classically, players can win this game with probability one if and only if a corresponding isomorphism does in fact exist. It is then natural to ask what happens when the players are allowed to make quantum measurements on a shared entangled state, i.e. are permitted to use "quantum strategies".