A survey on Hedetniemi's conjecture (Q1387740)

The product \(G\times H\) of the graphs \(G\) and \(H\) has vertex set \[ V(G\times H)= \{(g, h)\mid g\in V(G)\text{ and }h\in V(H)\} \] and edge set \[ E(G\times H)= \{(g, h)(g', h')\mid gg'\in E(G)\text{ and }hh'\in E(H)\}. \] It is easily seen that \(\chi(G\times H)\leq \min\{\chi(G), \chi(H)\}\); \textit{Hedetniemi} [University of Michigan Technical Report 03105-44-T (1966)] conjectured that equality holds for all finite simple graphs \(G\) and \(H\). An equivalent formulation is given by \(C(n)\): If graphs \(G\) and \(H\) are not \(n\)-colorable then the product \(G\times H\) is not \(n\)-colorable. Hedetniemi [ibid.] proved \(C(2)\). \textit{M. El-Zahar} and \textit{N. W. Sauer} [Combinatorica 5, 121-126 (1985; Zbl 0575.05028)] gave a complicated proof of \(C(3)\); the conjecture is open for \(n\geq 4\). The author gives a somewhat simplified version of their proof and then discusses results and problems related to the conjecture.