Graph Homomorphisms for Quantum Players

Understand

A homomorphism from a graph $X$ to a graph $Y$ is an adjacency preserving mapping $f:V(X) \rightarrow V(Y)$.

• We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph $X$ admits a homomorphism to $Y$.
• This is a generalization of the well-studied graph coloring game.
• Via systematic study of quantum homomorphisms we prove new results for graph coloring.