Hedetniemi's conjecture (1966): the chromatic number of a tensor product of graphs equals the minimum of the factors' chromatic numbers.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Assessment
Renown 4/5
A famous 1966 coloring conjecture, believed by most of the field for 53 years.
Attackability 1/5
Counterexamples are astronomically large exponential graphs; no search would have found them. Fell to insight.
- finite witness
- 3/5
- oracle cost
- 1/5
- freshness
- 1/5
- seedability
- 1/5
Confirmed resolution
counterexample by Yaroslav Shitov on .
Refuted after 53 years via exponential graphs; published in Annals of Mathematics. The counterexamples are enormous but the argument is three pages.
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
Confirmed
This entry no longer accepts claims or resolution reports.