4 Quantum Color Conjecture

1. The game

Quantum coloring is a two-player nonlocal game. Fix a graph \(G\) and a number of colors \(c\). A referee draws a pair of vertices \(x,y\), sends \(x\) to Alice and \(y\) to Bob, and receives colors \(a\) and \(b\). The players fix a strategy and share an entangled state before the questions are sent, and do not communicate afterwards. The round is won if \(a=b\) whenever \(x=y\), and \(a\neq b\) whenever \(x\sim y\). Other pairs impose no condition. The quantum chromatic number \(\chi_q(G)\) is the least \(c\) admitting a strategy that wins every pair with probability \(1\). The definition is due to Cameron, Montanaro, Newman, Severini and Winter, whose results are used throughout.

The same-vertex condition forces a classical strategy to assign a fixed color to each vertex, so a perfect classical strategy is a proper coloring and the least such \(c\) is \(\chi(G)\). A perfect quantum strategy is a family of projective measurements: for each vertex \(v\), projectors \(P_{v,1},\ldots,P_{v,c}\) satisfying

Adjacent vertices assign orthogonal subspaces to each color. In normal form all projectors have a common rank \(r\), and the local space has dimension \(cr\). The number of answers is \(c\) for every \(r\); the rank controls the available dimension only.

Fix one color on a clique of size \(k\). The \(k\) projectors for that color are pairwise orthogonal and each has rank \(r\), so \(kr\le cr\) and \(c\ge k\). Hence

2. Statement

The Four Color Theorem gives \(\chi(G)\le4\), and \(\chi_q\le\chi\) holds for every graph. \(\chi_q=1\) holds only for edgeless graphs, and \(\chi_q=2\) is equivalent to \(\chi=2\). The conjecture fails if and only if some planar \(H\) satisfies

I expect the statement to hold. The supporting evidence is limited to the cases in Section 3. I have no proof, and located no proof and no counterexample in the literature through July 2026.

3. Known results

Rank one. Assume every projector has rank \(1\). The projectors at a vertex \(v\) then form an orthonormal basis of \(\mathbb{C}^c\); collect it into a unitary \(U_v\). The edge condition states that \(U_v^{\dagger}U_w\) has zero diagonal. For \(c=3\), a zero-diagonal \(3\times3\) unitary is a permutation matrix with phases on its nonzero entries. Products of phased permutations are phased permutations, so setting \(U_{v_0}=I\) and propagating along a connected graph makes every \(U_v\) a phased permutation. Recording which coordinate vector the first column is proportional to gives a proper \(3\)-coloring. Hence

for all graphs. This is Proposition 11 of the original paper. Since \(\chi_q^{(1)}\le\chi\), a planar graph with \(\chi=4\) has \(\chi_q^{(1)}=4\): the conjecture holds in the rank-one model.

Rank one is not enough. The rank-one and unrestricted parameters differ. Lalonde (2025) exhibits a graph \(G_{21}\) on \(21\) vertices with \(\chi_q=\chi_q^{(2)}=4\) and \(\xi=\chi_q^{(1)}=\chi=5\), the first provable separation between \(\chi_q^{(1)}\) and \(\chi_q^{(2)}\). The previous paragraph therefore does not extend, and the conjecture is not a corollary of Proposition 11.

Three colors do separate. The graph \(G_{\mathrm{msg}}\) on \(57\) vertices satisfies

It is obtained by applying Karp's reduction from 3-SAT to 3-COL to the system of equations defining the magic square game, and is due to Mančinska and Roberson (2016). So the pattern \(\chi_q=3<4=\chi\) is realized. A planar counterexample requires this pattern, and it is therefore not excluded in general.

\(G_{\mathrm{msg}}\) is not planar. The Four Color Theorem does not apply, since \(\chi(G_{\mathrm{msg}})=4\). The reduction supplies three mutually adjacent vertices \(T\), \(F\), \(B\); every literal vertex is adjacent to \(B\); every constraint gadget is connected and meets \(T\), \(F\), and a literal. Fix three gadgets. Each meets \(T\) and \(F\) within itself and reaches \(B\) through its literal, along paths internally disjoint from those of the other two. Three gadgets against \(T\), \(F\), \(B\) is a subdivision of \(K_{3,3}\).

A separation at four colors. The original paper exhibits a graph on \(18\) vertices and \(44\) edges with \(\chi=5\) and \(\chi_q=\chi_q^{(1)}=4\); the quantum \(4\)-coloring comes from an orthogonal representation in \(\mathbb{R}^4\), and a \(4\)-clique supplies the matching lower bound. That graph is not planar, since \(\chi=5\) exceeds the Four Color bound.

Separations are not small. The smallest graph with \(\chi_q<\chi\) is \(G_{14}\) on \(14\) vertices, with \(\chi_q=4\) and \(\chi=5\), given by Mančinska and Roberson; Lalonde proved its minimality by computer search. Theorem 1.1 of that paper is sharper: any graph with \(\chi_q<\chi\) has at least \(15\) vertices, or exactly \(14\) vertices and \(\chi_q\ge4\). A graph with \(\chi_q=3<\chi\) therefore has at least \(15\) vertices.

Odd wheels. Let \(W_{2m+1}\) have hub \(h\) and rim \(v_1,\ldots,v_{2m+1}\), and assume a quantum \(3\)-coloring exists. Each triangle \(\{h,v_i,v_{i+1}\}\) is a \(3\)-clique under \(3\) colors, so for every color \(a\),

The rim has odd length, so steps of size two visit every rim vertex and all rim projectors for color \(a\) coincide. Adjacency then gives \(P_{v_i,a}=P_{v_i,a}^2=P_{v_i,a}P_{v_{i+1},a}=0\) for every \(a\), contradicting \(\sum_a P_{v_i,a}=I\). Hence \(\chi_q(W_{2m+1})=4\), and the conjecture holds on every odd wheel.

4. Constraints on a counterexample

Let \(H\) be a minimal planar graph with \(\chi_q(H)=3<\chi(H)=4\). Then:

1. \(H\) is \(4\)-critical, by passing to a minimal \(4\)-chromatic subgraph.
2. \(H\) is \(K_4\)-free, by the clique bound of Section 1.
3. \(H\) contains a triangle, since triangle-free planar graphs are \(3\)-colorable by Grötzsch's theorem.
4. \(H\) contains no odd wheel.
5. \(H\) has at least \(15\) vertices, by Theorem 1.1 of Lalonde (2025).
6. Every quantum \(3\)-coloring of \(H\) uses projectors of rank at least \(2\), by Proposition 11.

5. Search

The two directions are not symmetric. Refutation requires a positive certificate: a planar \(4\)-critical graph together with an explicit assignment of rank-\(r\) projectors on \(\mathbb{C}^{3r}\) satisfying the edge conditions, for some fixed \(r\). At fixed \(r\) this is decidable. It is a system of quadratic equations over the reals in dimension \(3r\), which the original paper notes can be handled by exact real-algebraic methods, and which is also open to semidefinite relaxation and to numerical search over unitary parametrizations. A certificate is verified directly from the two conditions in Section 1. Candidate generation is exhaustive: planar \(4\)-critical graphs on \(15\) or more vertices can be enumerated and filtered by the conditions in Section 4.

A proof is not a finite search. \(\chi_q=\inf_r \chi_q^{(r)}\), and no bound on the \(r\) needed to attain the infimum is known; the original paper identifies this as the obstruction to deciding \(\chi_q\). A proof would require a structural argument specific to planar graphs. Proposition 11 does not extend to higher rank, and \(\chi_q=3<4=\chi\) already occurs, so the argument cannot come from the number of colors alone. A search that terminates without a counterexample is not evidence for the conjecture.