Graph homomorphisms for quantum players

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...

Полное описание

Библиографические подробности
Главные авторы: Mančinska, Laura, Roberson, David
Другие авторы: School of Physical and Mathematical Sciences
Формат: Journal Article
Язык:English
Опубликовано: 2018
Предметы:
Online-ссылка:https://hdl.handle.net/10356/87672
http://hdl.handle.net/10220/46786