The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable (Q1063621)

\textit{S. Hedetniemi} [Homomorphisms of graphs and automata, Univ. of Michigan Technical Report 03105-44-T (1966)] has conjectured that, for finite graphs G and H, the Cartesian product \(G\times H\) satisfies the relation \(\chi (G\times H)=\min \{\chi (G),\chi (H)\}\). This note shows that, for infinite graphs, this relation need not hold. In particular, the main result is that, for every infinite cardinal \(\aleph\), there are graphs G and H such that \(\chi (G\times H)=\aleph\), but both \(\chi\) (G) and \(\chi\) (H) equal \(\aleph^+\), the least cardinal exceeding \(\aleph\).