Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the quantum chromatic number of a graph. | On the quantum chromatic number of a graph Peter J. Cameron Ashley Montanaroy Michael W. Newmanz Simone Severini x Andreas Winter Submitted Oct 31 2006 Accepted Sep 30 2007 Published Nov 28 2007 Mathematics Subject ClassiEcation 05C15 Abstract 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 Erst 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 End 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. 1 Introduction We consider an extension of graph colouring based on the following model. Fix some graph G and an integer c. Alice and Bob are each given a vertex of G and are to respond with an integer in c 0 1 . c 1g. They are required to answer differently if their vertices are adjacent and identically if their vertices are equal. They are allowed to agree on a joint strategy beforehand which may depend on G but not on the particular vertices they are given in particular they are not allowed to communicate in any way once they are given their vertices. School of Mathematical Sciences Queen Mary University of London London E1 4NS . y Department of Computer Science University of Bristol Bristol BS8 1UB . montanar@ zSchool of Mathematical Sciences Queen Mary University of London London E1 4NS . xDepartment of Mathematics University of York York YO10
