The chromatic number of the product of two 4-chromatic graphs is 4 (Q1063620)

The product \(G\times H\) of two graphs G and H is the graph whose vertex set is \(V(G)\times V(H)\) and whose edge set consists of all pairs \(((a,b), (\bar a,\bar b))\) such that \((a,\bar a)\) and \((b,\bar b)\) are edges of G and H respectively. The chromatic number of the product is early seen to satisfy the bound \(\chi(G\times H)\leq \min\{\chi(G),\chi(H)\}\). \textit{S. Hedetniemi} [Homomorphisms of graphs and automata, Univ. of Michigan Technical report 03105-44-T (1966)] has conjectured that equality holds in this bound, verifying this when the right-hand side is 3. The present paper verifies this conjecture when the right-hand side is 4.