On the Quantum Chromatic Number of a Graph
On the Quantum Chromatic Number of a Graph
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 …