For all finite graphs G and H, the quantum chromatic number of their categorical product satisfies chi_q(G× H)=minchi_q(G),chi_q(H), where G× H has vertex set V(G)× V(H) and (g,h) is adjacent to (g',h') exactly when g is adjacent to g' in G and h is adjacent to h' in H.

Quantum Hedetniemi conjecture

The conjecture asserts that the quantum chromatic number of a graph product equals the smaller quantum chromatic number of its factors: $\chi_q(G \times H)=\min\{\chi_q(G),\chi_q(H)\}$ .

Known results

A 2013 paper proves the formula when each factor satisfies $\chi_q=\bar{\vartheta}$ , including orthogonality graphs, but states that the general conjecture remained unproved.
The same paper proves the quantum analogue for Cartesian products: $\chi_q(G \square H)=\max\{\chi_q(G),\chi_q(H)\}$ .
A 2014 paper develops commuting, approximate, and related quantum chromatic parameters without resolving this conjecture.

September 2026 counterexample

A preprint by Julius A. Zeiss claims a counterexample, with graph constructions, certificates, and projective statements formalized in Lean 4. It claims simultaneous refutations for spatial, approximate, commuting-operator, and $C^*$ -algebraic quantum chromatic numbers; this claim is unverified.

Current status (as of September 2026): The classical special cases are established, while a September 2026 preprint claims to refute the conjecture and its listed variants, but the counterexample has not been independently verified.

Quantum Hedetniemi conjecture

Primary source

Additional references

Progress summary

Solutions 0