Hedetniemi's conjecture

Remarks

The inequality $\chi(G \times H) \le \min(\chi(G), \chi(H))$ always holds. Indeed, the projection $(g, h) \mapsto g$ is a graph homomorphism to $G$, so a proper colouring of $G$ pulls back to one of $G \times H$. The same holds for $H$. Shitov's counterexample uses an exponential graph. For a graph $G$ and $c \ge 1$, the vertices of $K_c^G$ are all maps $f \colon V(G) \to \set{1, \dots, c}$. Two maps $f$ and $f'$ are adjacent when $f(u) \ne f'(v)$ for every edge $uv$ of $G$, in both orders of $u$ and $v$. The map $(v, f) \mapsto f(v)$ is a proper colouring of $G \times K_c^G$ with $c$ colours. Indeed, if $(u, f)$ and $(v, f')$ are adjacent, then $uv$ is an edge and $f$ is adjacent to $f'$, so $f(u) \ne f'(v)$. So any $G$ with $\chi(G) > c$ and $\chi(K_c^G) > c$ is a counterexample, and Shitov showed that such $G$ exist for large $c$. The conjecture holds when $\min(\chi(G), \chi(H)) \le 4$; the case $4$ is a theorem of El-Zahar and Sauer.