Hedetniemi's conjecture for graphs with countable chromatic number

Question

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

Answer 1

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.

Answer 2

No; this is a theorem of Hajnal. Suppose $G$ is a graph such that $\chi(G)$ is infinite, and say that a set of vertices of $G$ is chromatically cofinite if the induced subgraph on the complement is finitely colorable. The collection of chromatically cofinite sets is a filter; extend it to an ultrafilter $U$. Note that every $A\in U$ (as an induced subgraph of $G$) has infinite chromatic number, and in particular has many edges.

Now suppose you have a proper $n$-coloring $\alpha:G\times H\to \{1,\dots,n\}$ for some graph $H$. For each $g\in G$, this determines a function $\alpha_g: H\to\{1,\dots,n\}$ given by $\alpha_g(h)=\alpha(g,h)$; let $\alpha_U:H\to\{1,\dots n\}$ be the limit of the $\alpha_g$ with respect to the ultrafilter $U$ (i.e. $\alpha_U(h)=i$ iff $\alpha_g(h)=i$ for a set of $g$ that is in $U$). Then $\alpha_U$ is a proper $n$-coloring of $H$. Indeed, if $h,h'\in H$ are adjacent and $\alpha_U(h)=\alpha_U(h')=i$, then the set $A=\{g:\alpha_g(h)=\alpha_g(h')=i\}$ is in $U$. We can thus find $g,g'\in A$ which are adjacent, and then $(g,h)$ is adjacent to $(g',h')$ in $G\times H$. But $\alpha(g,h)=\alpha(g',h')=i$ and $\alpha$ is a proper coloring of $G\times H$, so this is a contradiction.