Graph homomorphisms for quantum players

• المؤلفون الرئيسيون: Mančinska, Laura, Roberson, David
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: 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...