1. The game

Quantum coloring is a two-player nonlocal game. Fix a graph \(G\) and a number of colors \(c\). Acme draws a pair of vertices \(x,y\), sends \(x\) to Doe and \(y\) to Roe, 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 quantum strategy is nothing but a shared state and two families of projectors. Doe holds a state space \(\mathcal{H}_D\) and, for each vertex \(v\), a projective measurement \(P_{v,1},\ldots,P_{v,c}\) on it; Roe holds \(\mathcal{H}_R\) and, for each vertex \(w\), a projective measurement \(Q_{w,1},\ldots,Q_{w,c}\). Together with a state \(|\psi\rangle\in\mathcal{H}_D\otimes\mathcal{H}_R\) fixed before the round, that is the entire strategy: on receiving \(x\), Doe measures \(\{P_{x,a}\}_a\) and returns the outcome, and Roe does the same with \(\{Q_{y,b}\}_b\). The answers are therefore distributed as

$$ \Pr[\,a,b \mid x,y\,] \;=\; \langle\psi|\,P_{x,a}\otimes Q_{y,b}\,|\psi\rangle , $$

and the strategy is perfect when this vanishes for \(a\neq b\) at \(x=y\) and for \(a=b\) at \(x\sim y\). Neither player's own answer is determined: on the maximally entangled state each color comes up with probability \(1/c\) at every vertex, and what the conditions constrain is the correlation between the two answers, not either one alone.

The two families collapse to one. A perfect strategy can be put in normal form: \(\mathcal{H}_D=\mathcal{H}_R=\mathbb{C}^{cr}\), the state maximally entangled, every \(P_{v,a}\) a projector of the same rank \(r\), and Roe's operators the entrywise conjugates \(Q_{w,b}=\overline{P_{w,b}}\) of Doe's. The probability above becomes \(\mathrm{Tr}(P_{x,a}P_{y,b})/cr\), so the two winning conditions reduce to conditions on the single family \(\{P_{v,a}\}\):

$$ \sum_{a=1}^{c} P_{v,a} = I, \qquad P_{v,a}P_{w,a} = 0 \quad\text{for every edge } v\sim w \text{ and every color } a. $$

This is why the rest of the article speaks only of \(P\): Roe's half of the strategy is determined by Doe's. Adjacent vertices assign orthogonal subspaces to each color, and \(\chi_q^{(r)}(G)\) is the least \(c\) admitting such a strategy at rank \(r\). Appendix A collects this and the rest of the notation.

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

$$ \omega(G)\;\le\;\chi_q(G)\;\le\;\chi(G). $$

2. Statement

$$ \chi_q(G) \;=\; \chi(G)\qquad\text{for every planar } G. $$

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

$$ \chi_q(H) \;=\; 3 \;<\; 4 \;=\; \chi(H). $$

I do not expect the statement to hold. \(G_{\mathrm{msg}}\) in Section 3 realizes \(\chi_q=3<4=\chi\), so the configuration the conjecture forbids is available in general. Planarity classically bounds the chromatic number from above; the conjecture requires it to bound \(\chi_q\) from below, since every planar graph with \(\chi=4\) would have to fail to be quantum \(3\)-colorable. The conditions defining a quantum coloring are orthogonality relations among projectors and refer to no embedding, so the conjecture would place planar graphs in a class that obstructs rank-\(\ge2\) projector assignments and has no classical analogue. I know of no mechanism that would produce such an obstruction. The cases in Section 3 are the only evidence in its favor, and I found 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

$$ \chi_q^{(1)}(G) = 3 \iff \chi(G) = 3, $$

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

$$ \chi_q(G_{\mathrm{msg}})=3,\qquad \chi_q^{(1)}(G_{\mathrm{msg}})=\xi(G_{\mathrm{msg}})=\chi(G_{\mathrm{msg}})=4. $$

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\),

$$ P_{h,a}+P_{v_i,a}+P_{v_{i+1},a}=I \quad\Longrightarrow\quad P_{v_i,a}=P_{v_{i+2},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\). 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.

The standard method for planar coloring theorems has no analogue here. \(\chi_q\) is monotone under graph homomorphisms and hence under subgraphs, but not under minors: \(C_5\) is a minor of \(C_6\), and \(\chi_q(C_5)=3>2=\chi_q(C_6)\). Since \(C_6\) is a subdivision of \(C_5\), the same example rules out monotonicity under topological minors. Classical \(\chi\) fails identically, so this alone does not separate the two problems. The separation is in the proof method itself.

The Four Color Theorem is proved by reducible configurations and discharging; Appendix B sets out both halves and where each one stands under \(\chi_q\). In short: discharging is a counting argument about planar triangulations that never mentions colorings, and it carries over unchanged. Reducibility is a finite check over the \(4\)-colorings of a bounded ring, and it does not carry over. The ring data for \(\chi_q\) is not a function into a finite set of colors but a family of rank-\(r\) projectors, forming a real algebraic variety at each \(r\) with no known bound on \(r\), so there is nothing to enumerate and no Kempe move to enumerate over. Deciding reducibility of a single configuration would subsume deciding whether a fixed finite graph is quantum \(3\)-colorable, which is open. What would replace it is a local algebraic obstruction valid at every rank — what the odd wheel argument of Section 3 supplies for one configuration and nothing supplies for the rest.

A search that terminates without a counterexample is not evidence for the conjecture.

References

  1. Cameron, Montanaro, Newman, Severini & Winter, on the quantum chromatic number of a graph, Electronic Journal of Combinatorics 14 (2007), #R81. Definition of \(\chi_q\) and \(\chi_q^{(r)}\), the clique bound (Proposition 4), \(\chi_q=2\iff\chi=2\) (Proposition 3), the rank-one theorem (Proposition 11), the \(18\)-vertex example, and the decidability remarks in Section 7.
  2. Mančinska & Roberson, oddities of quantum colorings, Baltic Journal on Modern Computing 4 (2016), no. 4, 846–859. The graphs \(G_{14}\) and \(G_{\mathrm{msg}}\).
  3. Lalonde, on the quantum chromatic numbers of small graphs, Electronic Journal of Combinatorics 32 (2025), #P1.18; arXiv:2311.08194. Minimality of \(G_{14}\), Theorem 1.1, and the graph \(G_{21}\).
  4. Robertson, Sanders, Seymour & Thomas, the four-colour theorem, Journal of Combinatorial Theory, Series B 70 (1997), no. 1, 2–44. The \(633\) reducible configurations, the \(32\) discharging rules, and the reducibility computation described in Appendix B.

Appendix A. Notation

Appendix B. The Four Color Theorem machinery

The method. The Four Color Theorem is proved by contradiction from a minimal counterexample \(G\): a planar graph that is not \(4\)-colorable, with the fewest vertices. Adding edges inside faces preserves planarity and only makes coloring harder, so \(G\) may be assumed to be a triangulation. Two independent facts are then established about triangulations, one about coloring and one about counting.

Configurations and reducibility. A configuration is a small labelled patch of a triangulation: a connected set of vertices \(K\), a prescribed degree in \(G\) for each vertex of \(K\), and the ring \(R\), the cycle of \(k\) vertices surrounding \(K\). Robertson, Sanders, Seymour and Thomas use \(633\) configurations, all with ring size \(k\le14\). A configuration is reducible if it cannot occur in a minimal counterexample. The argument runs: delete the interior \(K\) from \(G\), possibly after contracting some edges inside it, leaving a planar graph \(G'\) with fewer vertices. By minimality \(G'\) is \(4\)-colorable. Any such coloring restricts to a proper \(4\)-coloring of the ring \(R\), and what remains is to extend that ring coloring across \(K\), which colors \(G\) and gives the contradiction. This step is a finite computation. The ring is a \(k\)-cycle, so it has exactly \(3^k+3(-1)^k\) proper \(4\)-colorings, fewer than \(5\times10^6\) at \(k=14\); for each one, whether it extends into \(K\) is decided by backtracking over the \(4^{|K|}\) assignments to the interior. Ring colorings that do not extend are handled by Kempe chains: fix two colors, take a connected component of the subgraph induced by the vertices carrying those two colors, and swap the colors on it. This yields another \(4\)-coloring of \(G'\) and so another ring coloring, and the configuration is reducible if every ring coloring reaches an extendable one by such swaps. Every object here is a finite set, and the search over them was performed by computer.

Discharging. The second fact is that those \(633\) configurations are unavoidable: every planar triangulation contains one. Give each vertex the charge \(6-\deg(v)\). A triangulation has \(|E|=3|V|-6\), so the total charge is \(6|V|-2|E|=12>0\). Fixed rules then move charge between vertices, from those of high degree to nearby ones of low degree; the proof above uses \(32\) such rules. Redistribution does not change the total, so after it some vertex still carries positive charge. One then checks, over the finitely many ways a vertex can end positive, that its neighborhood must contain one of the \(633\) configurations. Combining the two facts closes the argument: \(G\) contains a configuration from the list, that configuration is reducible, so \(G\) is not a minimal counterexample and none exists.

Where \(\chi_q\) breaks this. Discharging survives intact. It is a statement about planar triangulations and never mentions colorings, so the same unavoidable set is available. Reducibility does not survive, for two reasons.

  1. The induction cannot route around the projectors. Let \(H\) be a minimal planar graph with \(\chi_q(H)=3<\chi(H)=4\) and let \(H'\) be \(H\) with the interior of a configuration deleted. Then \(\chi_q(H')\le\chi_q(H)=3\) by subgraph monotonicity, and \(H'\) is smaller, so by minimality it is not a counterexample and \(\chi(H')\le3\). A configuration that let every proper \(3\)-coloring of the ring extend across \(K\) would give \(\chi(H)\le3\). But an unavoidable set of such configurations would prove every planar graph \(3\)-colorable, which is false. The hypothesis \(\chi_q(H)=3\) must therefore enter through the projectors themselves, not through the classical coloring of the smaller graph.
  2. The boundary data is not finite. Classically the restriction of a coloring to the ring is a function \(R\to\{1,2,3,4\}\), one of finitely many. Quantumly the restriction of a quantum \(3\)-coloring to the ring assigns to each \(v\in R\) a triple of rank-\(r\) projectors \((P_{v,1},P_{v,2},P_{v,3})\) on \(\mathbb{C}^{3r}\) with \(\sum_a P_{v,a}=I\) and \(P_{v,a}P_{w,a}=0\) along the ring. At fixed \(r\) these form a real algebraic variety rather than a finite set — conjugating every projector by one unitary already produces a continuum — and \(r\) is not bounded, since \(\chi_q=\inf_r\chi_q^{(r)}\) with no known bound on the \(r\) attaining the infimum. So there is nothing to enumerate, and fixing \(r\) to recover finiteness proves nothing about \(\chi_q\). Kempe chains are also unavailable: a quantum coloring assigns no color to any vertex, every vertex carrying all three projectors at once, so "the component of vertices colored \(1\) or \(2\)" does not parse.

Reducibility of a single configuration is therefore not merely expensive but not known to be decidable, since it subsumes deciding whether a fixed finite graph admits a quantum \(3\)-coloring. What would be needed in its place is a local algebraic obstruction for each configuration, valid at every rank — an argument shaped like the odd wheels of Section 3, where the identity \(P_{h,a}+P_{v_i,a}+P_{v_{i+1},a}=I\) does the work of the finite check and refers to \(r\) nowhere. I know of no such argument for any other configuration.