---
tag: 4H1HA9BX5T
kind: statement
role: proposition
name: Weak Hedetniemi Conjecture
sources:
  - wikipedia: en:8155146@r1353005739
    locator: Hedetniemi's conjecture, section Weak Hedetniemi Conjecture
    note: adopted
    mention: wikipedia://en/8155146#UN6W
    sections: [Statement]
inventory: [JJ0K9HZV2N]
---

## 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.