A counterexample to the quantum Hedetniemi conjecture
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× H) ≤ 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.
Related
- Hedetniemi's Conjecture for Uncountable Complementary Graphs
- Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
- A counterexample to a conjecture of Duncan on versal actions
- A Counterexample to the Eventual Stability Conjecture
- A non-klt counterexample to Shokurov's index conjecture
BibTeX
@misc{zeiss2026counterexample,
title = {{A counterexample to the quantum Hedetniemi conjecture}},
author = {Julius A. Zeiss},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20690},
eprint = {2609.20690},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20690},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A counterexample to the quantum Hedetniemi conjecture
AU - Julius A. Zeiss
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20690
UR - https://arxiv.org/abs/2609.20690
AB - 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× H) ≤ 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.
ER -