Graph homomorphisms for quantum players

• Main Authors: Mančinska, Laura, Roberson, David
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2018
• 主題: Graph Homomorphism; Nonlocal Game; DRNTU::Science::Physics
• 在線閱讀: https://hdl.handle.net/10356/87672; http://hdl.handle.net/10220/46786
• 機構: 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...