A counterexample to the quantum Hedetniemi conjecture
Julius A. Zeiss
math.CO
Sep 17, 2026 · v1
quant-ph
TL;DR
Graph constructions, exact-integer certificates, and the projective counterexample statements are formalized and verified in Lean 4 with Mathlib.
Abstract
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean 4.
Problem
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the factors' quantum chromatic numbers. Whether this quantum Hedetniemi conjecture holds was open.
Approach
Explicit finite graphs G,H are constructed from Zhu's Hedetniemi counterexample using a base Cayley graph on F_2^10 whose complement has large Lovász theta number. The first factor's lower bound is the theta bound proved in an arbitrary nonzero unital C*-algebra; the second adapts Zhu's argument to noncommuting projections via operator identities. A product coloring supplies the upper bound. The graph constructions, integer certificates, and projective statements are formalized in Lean 4.19.0 with Mathlib.
Results
They construct G,H with chi(G×H) ≤ 1538 < 1539 = min(chi_q(G),chi_q(H)), disproving the conjecture and its spatial, approximate, commuting-operator and C*-algebraic variants. Smaller counterexamples certified by exact integer data are also given.
