Are there graphs $G, H$ such that $\chi(G) = \chi(H) = \aleph\_0$, but $\chi(G\times H) < \aleph\_0$? 



Hedetniemi's conjecture for graphs with countable chromatic number
The existence of such a pair of graphs would contradict Hedetniemi's conjecture for finite graphs. 


Suppose $\chi(G \times H) = k < \aleph\_0$ then $\chi(G\_0 \times H\_0) \leq k$ for all finite induced subgraphs $G\_0$ and $H\_0$ of $G$ and $H$, respectively. If $\chi(G) > k$ then this is witnessed by a finite induced subgraph $G\_0$ of $G$. Assuming Hedetniemi's conjecture, we must then have $\min(\chi(G\_0),\chi(H\_0)) = \chi(G\_0 \times H\_0) \leq k$ for every finite induced subgraph $H\_0$ of $H$. Since $\chi(G\_0) > k$, we must have $\chi(H\_0) \leq k$. But then $H$ must be $k$-colorable since every finite induced subgraph of $H$ is $k$-colorable.


In other words, the above shows that if Hedetniemi's conjecture holds for all finite graphs, then it also holds for infinite graphs when at least one of the factors is finitely or countably colorable.


In fact, one can say more about the exact relationship with Hedetniemi's conjecture. Consider the function $$h(n) = \min\{\chi(G \times H) : \chi(G), \chi(H) \geq n\}.$$ On the one hand, Hedetniemi's conjecture is equivalent to $h(n) = n$ for all $n$. On the other hand, the existence of two graphs $G, H$ with $\chi(G), \chi(H) \geq \aleph\_0$ and $\chi(G \times H) < \aleph\_0$ is equivalent to the statement that $h$ is bounded.


