Let G and H be finite undirected simple graphs. Their tensor product G× H is the graph with vertex set V(G)× V(H) in which (u,v) and (u',v') are adjacent if and only if uu'∈ E(G) and vv'∈ E(H). Write chi(G) for the chromatic number of a graph. Hedetniemi's conjecture. chi(G× H)=minchi(G),chi(H). The equality was disproved by counterexamples constructed by Shitov, who showed that for sufficiently large k there are infinitely many pairs (G,H) with minchi(G),chi(H)>k and chi(G× H)=k.

Hedetniemi's conjecture on the chromatic number of tensor products

From papers

Let $G$ and $H$ be finite undirected simple graphs. Their tensor product $G\times H$ is the graph with vertex set $V(G)\times V(H)$ in which $(u,v)$ and $(u',v')$ are adjacent if and only if $uu'\in E(G)$ and $vv'\in E(H)$ . Write $\chi(G)$ for the chromatic number of a graph.

Hedetniemi's conjecture.

\chi(G\times H)=\min\{\chi(G),\chi(H)\}.

The equality was disproved by counterexamples constructed by Shitov, who showed that for sufficiently large $k$ there are infinitely many pairs $(G,H)$ with $\min\{\chi(G),\chi(H)\}>k$ and $\chi(G\times H)=k$ .

Progress summary

Solved

Shitov’s 2019 counterexample showed that the proposed equality is false, and later work quantified how far the product’s chromatic number can fall.

Stephen T. Hedetniemi posed the conjecture in 1966, asserting equality between the chromatic number of a tensor product and the smaller chromatic number of its factors. Yaroslav Shitov disproved it in 2019 by constructing finite simple graphs with $\chi(G\times H)<\min\{\chi(G),\chi(H)\}$ .

Known results

The conjecture holds when one factor has chromatic number at most $4$ (classical work, reported in 2019).
The cases $c\le 2$ are immediate, and the $c=3$ case was proved by El-Zahar and Sauer.
The fractional analogue is true: $\chi_f(G\times H)=\min\{\chi_f(G),\chi_f(H)\}$ .

2019–2026 quantitative counterexamples

Shitov’s construction was followed by smaller examples. He and Wigderson (2021) proved a constant-factor separation: for some absolute $\delta>0$ and all sufficiently large $c$ , both factors have chromatic number at least $(1+\delta)c$ while the product has chromatic number at most $c$ . For the related weak problem, later work improved the asymptotic bound to $f(n)\le\lceil n/2\rceil+3$ (Tardif, reported 2026); this does not alter the original conjecture’s settled status.

Current status (as of August 2026): The original conjecture is disproved and resolved; its positive low-chromatic and fractional variants remain valid, while related weak asymptotic questions continue to develop.

Sources

Sources & referencesView supporting material

Primary source

Ryoya Fukasaku, Michitaka Furuya and Akihiro Higashitani, “An algebraic reduction of Hedetniemi's conjecture”, arXiv:1911.09799 (2019).

Additional references

9 papers in this index state this conjecture (2009–2019). The statement above is taken from the most recent of them; the others are arXiv:1810.00648, arXiv:1803.01505, arXiv:1710.05290, arXiv:1608.02918, arXiv:1305.5545, arXiv:1305.4237, arXiv:1202.5720, arXiv:0905.1200.

graph-coloring graph-products

1 week ago