The problem
Claim: χ(G × H) = min(χ(G), χ(H)) for the tensor (categorical) product of finite graphs — i.e. a product is k-colourable iff at least one factor is.
Hedetniemi's Conjecture
historicReferences
History & significance
Posed 1966; verified across enormous classes (products involving 4-chromatic graphs, multiplicative graphs à la Greenwell–Lovász). The conjecture anchored a whole subfield of graph homomorphisms — Pultr, Hell, Nešetřil built multiplicativity theory around it.
The resolution (human proof)
Disproved May 2019 by Yaroslav Shitov: a construction of counterexample graphs whose product needs fewer colours than either factor — short enough to read in an evening, deep enough to require the full modern homomorphism toolkit. Published in Annals of Mathematics the same year. A modern classic of how a universally believed statement dies: not by erosion, but by a cleaner idea.