Coloring an Orthogonality Graph

DOI10.1137/050639715zbMATH Open1167.05314arXivmath/0509151OpenAlexW2120490860MaRDI QIDQ3629469FDOQ3629469

Authors: Chris Godsil, Mike Newman 

Publication date: 27 May 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a $pm1$-vector of length $k$, and are to respond with $k$ bits. Their responses must be equal if they are given equal inputs, and distinct if they are given orthogonal inputs; however, they are not allowed to communicate any information about their inputs. They can always succeed using quantum entanglement, but their ability to succeed using only classical physics is equivalent to a graph colouring problem. We resolve the graph colouring problem, thus determining that they can succeed without entanglement exactly when $kleq3$.

Full work available at URL: https://arxiv.org/abs/math/0509151

Recommendations

• Orthogonal colorings of graphs
• Colorability in Orthogonal Graph Drawing
• scientific article; zbMATH DE number 4008416
• Orthogonal colourings of Cayley graphs
• Orthogonal vector coloring
• Colorings and orientations of graphs
• Oriented graph coloring
• scientific article; zbMATH DE number 3935075
• Graph colorings
• Colorings and orientations of matrices and graphs

zbMATH Keywords

graph coloringmaximum independent setsorthogonality graphratio boundquantum telepathy

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cited In (16)

• Violating the Shannon capacity of metric graphs with entanglement
• Colorability in Orthogonal Graph Drawing
• Orthogonal vector coloring
• Orthogonal colorings of graphs
• The orthogonal colouring game
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• Noncontextual coloring of orthogonality hypergraphs
• The automorphism group and fixing number of orthogonality graph over a vector space
• Classical, quantum and nonsignalling resources in bipartite games
• Orthogonal colourings of Cayley graphs
• Quantum contextuality with stabilizer states
• Commutative association schemes
• Distinguishing orthogonality graphs
• Deterministic quantum non-locality and graph colorings
• Towards characterizing the non-locality of entangled quantum states

This page was built for publication: Coloring an Orthogonality Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3629469)