Mančinska-Roberson Graphs

The Mančinska-Roberson graphs are two graphs introduced by Mančinska and Roberson (2016) in the study of quantum colorings. The first is a 13-vertex, 24-edge orthogonality graph of the nonzero vectors in ${-1,0,1}^3$ modulo overall sign, also known as the magic cube orthogonality graph (House of Graphs, Yu and Oh 2012) and the Yu-Oh 13-ray graph (Yu and Oh 2012, Cabello et al. 2016). The second is the 14-vertex, 37-edge cone graph obtained by adjoining one apex vertex to the first graph.

The 14-vertex Mančinska-Roberson graph has ordinary chromatic number 5 but quantum chromatic number 4 (Mančinska and Roberson 2016). Lalonde (2025) showed that it is the smallest graph, by number of vertices, for which these two numbers differ.

The Mančinska-Roberson graphs will be implemented in a future version of the Wolfram Language as GraphData["MancinskaRobersonGraph13"] and GraphData["MancinskaRobersonGraph14"].

Explore with Wolfram|Alpha

More things to try:

References

Cabello, A.; Kleinmann, M.; and Portillo, J. R. "Quantum State-Independent Contextuality Requires 13 Rays." J. Phys. A: Math. Theor. 49, 38LT01, 2016. https://doi.org/10.1088/1751-8113/49/38/38LT01.House of Graphs. "Orthogonality Graph of Magic Cube." https://houseofgraphs.org/graphs/18432.Lalonde, O. "On the Quantum Chromatic Numbers of Small Graphs." Elec. J. Combin. 32, No. 1, P1.18, 1-26, 2025. https://doi.org/10.37236/12506.Mančinska, L. and Roberson, D. E. "Oddities of Quantum Colorings." Baltic J. Modern Computing 4, 846-859, 2016. https://doi.org/10.22364/bjmc.2016.4.4.16.Yu, S. and Oh, C. H. "State-Independent Proof of Kochen-Specker Theorem with 13 Rays." Phys. Rev. Lett. 108, 030402, 2012. https://doi.org/10.1103/PhysRevLett.108.030402.

Cite this as:

Weisstein, Eric W. "Mančinska-Roberson Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Mancinska-RobersonGraphs.html

Mančinska-Roberson Graphs

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications