Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme

Switch Atlas

Conjecture

Hedetniemi's Conjecture

Combinatorics

Hedetniemi's conjecture, formulated by Stephen Hedetniemi in 1966, concerned the relationship between graph coloring and the tensor product of graphs, stating that the chromatic number of the tensor product of two graphs G and H equals the smaller of the chromatic numbers of G and H. A counterexample discovered by Yaroslav Shitov in 2019 disproved the conjecture in general.

Facts
Statement
Hedetniemi's conjecture proposed that the chromatic number of the tensor product of two finite graphs equals the smaller of the two graphs' own chromatic numbers. 1
Proposed Year
1966 1
Progress Toward Resolution
The conjecture was disproved in general by Yaroslav Shitov in 2019, who found a counterexample. Before the disproof it had been confirmed for restricted cases: it holds whenever one of the two graphs is bipartite, and El-Zahar and Sauer proved in 1985 that it holds whenever the tensor product is 3-colorable. 1
Open Questions
Prize Status
No prize is recorded.
No source consulted this pass names a monetary prize for this conjecture.
Prize Status (category)
No Prize Offered
w-freetextdim2b-0926: category derived from a free-text property; original status/verification detail carried on the source property.
Classification
Resolution Status
Disproven 1
Chronology
Resolved Year
2019 2
Connections

In Branch

Graph Theory, Branches of Mathematics
Source Hedetniemi's Conjecture (Wikipedia)
Sources
1. Hedetniemi's Conjecture (Wikipedia)
Wikimedia Foundation
  • Lead section
    A counterexample to the conjecture was discovered by Yaroslav Shitov (2019) (see Kalai 2019), thus disproving the conjecture in general.
  • In Branch: Graph Theory, Lead sentence
    In graph theory, Hedetniemi's conjecture, formulated by Stephen T.
View the Source
2. Hedetniemi's conjecture (Wikipedia)
A counterexample to the conjecture was discovered by Yaroslav Shitov (2019), thus disproving the conjecture in generalView the Source
Frequently Asked Questions

Is Hedetniemi's conjecture true?

No; Shitov disproved it in 2019.

No. Yaroslav Shitov found a counterexample in 2019, which disproved the conjecture in general. The claim that the chromatic number of the tensor product of two graphs equals the smaller of their chromatic numbers had stood since Stephen Hedetniemi formulated it in 1966.
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.