id: 05540859
dt: j
an: 05540859
au: Cameron, Peter J.; Montanaro, Ashley; Newman, Michael W.; Severini, Simone;
    Winter, Andreas
ti: On the quantum chromatic number of a graph.
so: Electron. J. Comb. 14, No. 1, Research Paper R81, 15 p. (2007).
py: 2007
pu: Prof. André Kündgen, Deptartment of Mathematics, California State
    University San Marcos, San Marcos, CA
la: EN
cc: 
ut: quantum chromatic number; chromatic number; clique number; separated
    provers; random graphs
ci: 
li: emis:journals/EJC/Volume_14/Abstracts/v14i1r81.html
ab: Summary: We investigate the notion of quantum chromatic number of a graph,
    which is the minimal number of colors necessary in a protocol on 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 14.
rv: