Graph homomorphisms for quantum players

• Main Authors: Mančinska, Laura, Roberson, David
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2018
• Subjects: Graph Homomorphism; Nonlocal Game; DRNTU::Science::Physics
• Online Access: https://hdl.handle.net/10356/87672; http://hdl.handle.net/10220/46786
• Institution: Nanyang Technological University

A homomorphism from a graph X to a graph Y is an adjacency preserving mapping f:V(X) -> 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...