Papers › On the Quantum Chromatic Numbers of Small Graphs
On the Quantum Chromatic Numbers of Small Graphs
Olivier Lalonde
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Man\v{c}inska and Roberson [\textit{Baltic Journal on Modern Computing}, 4(4), 846-859, 2016] gave an example of a graph G₁₄ on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-r quantum chromatic numbers. While it can now be shown that for every r, χ_q and χ⁽ʳ⁾_q are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph G₂₁ on 21 vertices with χ_q(G₂₁) = χ⁽²⁾_q(G₂₁) = 4 and ξ(G₂₁) = χ⁽¹⁾_q(G₂₁) = χ(G₂₁) = 5. The previous record was held by a graph G_(msg) on 57 vertices that was first considered in the aforementioned paper of Man\v{c}inska and Roberson and which satisfies χ_q(G_(msg)) = 3 and χ⁽¹⁾_q(G_(msg)) = 4. In addition, G₂₁ provides the first provable separation between the parameters χ⁽¹⁾_q and χ⁽²⁾_q. We believe that our techniques for constructing G₂₁ and lower bounding its orthogonal rank could be of independent interest.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections