Geodesic
On the quantum chromatic number of a graph
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince a referee that they have a colouring of the graph.After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is $2$, nor if it is $3$ in a restricted quantum model; on the other hand, we exhibit a graph on $18$ vertices and $44$ edges with chromatic number $5$ and quantum chromatic number $4$.
DOI : 10.37236/999
Classification : 05C15, 05C80, 05C85, 68M12, 81P68
Mots-clés : quantum chromatic number, chromatic number, clique number, separated provers, random graphs 
Peter J. Cameron; Ashley Montanaro; Michael W. Newman; Simone Severini; Andreas Winter. On the quantum chromatic number of a graph. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/999
@article{10_37236_999,
     author = {Peter J. Cameron and Ashley Montanaro and Michael W. Newman and Simone Severini and Andreas Winter},
     title = {On the quantum chromatic number of a graph},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/999},
     zbl = {1182.05054},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/999/}
}
TY  - JOUR
AU  - Peter J. Cameron
AU  - Ashley Montanaro
AU  - Michael W. Newman
AU  - Simone Severini
AU  - Andreas Winter
TI  - On the quantum chromatic number of a graph
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/999/
DO  - 10.37236/999
ID  - 10_37236_999
ER  - 
%0 Journal Article
%A Peter J. Cameron
%A Ashley Montanaro
%A Michael W. Newman
%A Simone Severini
%A Andreas Winter
%T On the quantum chromatic number of a graph
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/999/
%R 10.37236/999
%F 10_37236_999

Cité par Sources :