← All problems

Quantum Hedetniemi conjecture

For all finite graphs GG and HH, the quantum chromatic number of their categorical product satisfies χq(G×H)=min⁡{χq(G),χq(H)}\chi_q(G\times H)=\min\{\chi_q(G),\chi_q(H)\}, where G×HG\times H has vertex set V(G)×V(H)V(G)\times V(H) and (g,h)(g,h) is adjacent to (g′,h′)(g',h') exactly when gg is adjacent to g′g' in GG and hh is adjacent to h′h' in HH.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A September 2026 preprint claims a formally checked counterexample that would disprove the quantum conjecture and several related versions, but independent verification is not recorded.

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

Known results

  • A 2013 paper proves the formula when each factor satisfies χq=ϑˉ\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: χq(G□H)=max⁡{χq(G),χq(H)}\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,. It claims simultaneous refutations for spatial, approximate, commuting-operator, and C∗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.

Sources

Solutions 0

No solutions have been posted yet.