  Motivated by non-local games and quantum coloring problems, we introduce a
graph homomorphism game between quantum graphs and classical graphs. This game
is naturally cast as a "quantum-classical game"--that is, a non-local game of
two players involving quantum questions and classical answers. This game
generalizes the graph homomorphism game between classical graphs. We show that
winning strategies in the various quantum models for the game is an analogue of
the notion of non-commutative graph homomorphisms due to D. Stahlke [44].
Moreover, we present a game algebra in this context that generalizes the game
algebra for graph homomorphisms given by J.W. Helton, K. Meyer, V.I. Paulsen
and M. Satriano [22]. We also demonstrate explicit quantum colorings of all
quantum complete graphs, yielding the surprising fact that the algebra of the
$4$-coloring game for a quantum graph is always non-trivial, extending a result
of [22].
