We associate to each synchronous game a *-algebra whose representations determine whether the game has a perfect deterministic strategy, perfect quantum strategy or one of several other types of strategies studied in the theory of non-local games. Applying these results to the graph coloring game allows us to develop a correspondence between various chromatic numbers of a graph and the question of whether ideals in a free algebra are proper; this latter question can then be approached via non-commutative Gröbner basis methods. Furthermore, we introduce several new chromatic numbers guided by the algebra. One of these new chromatic numbers, χ_alg, is called the algebraic chromatic number, and one of our main results is the algebraic 4-colorability theorem: all graphs G satisfy χ_alg(G) ≤ 4.

The first and second-named authors have been supported in part by NSF DMS-1500835. The third and fourth-named authors are supported in part by NSERC Discovery Grants