Weak Hedetniemi Conjecture

Statement

The following function (known as the Poljak-Rödl function) measures how low the chromatic number of products of n-chromatic graphs can be.

$$f(n) = \min\{ \chi (G \times H) \colon \chi (G) = \chi (H) = n \}$$

Hedetniemi's conjecture is then equivalent to saying that $f(n) = n$. The Weak Hedetniemi Conjecture instead states merely that the function f(n) is unbounded. In other words, if the tensor product of two graphs can be colored with few colors, this should imply some bound on the chromatic number of one of the factors.

The main result of (Poljak Rödl 1981), independently improved by Poljak, James H. Schmerl, and Zhu, states that if the function f(n) is bounded, then it is bounded by at most 9. Thus a proof of Hedetniemi's conjecture for 10-chromatic graphs would already imply the Weak Hedetniemi Conjecture for all graphs.