Hedetniemi's Conjecture for Uncountable Complementary Graphs

Abstract

We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph $G$ and its complement $\overline{G}$ are both uncountably chromatic while their categorical product is countably chromatic, then $|V(G)|=\omega_1$. Assuming $\diamondsuit$, we construct a graph $G$ on $\omega_1$ such that $\chi(G)=\chi(\overline{G})=\omega_1$ and $\chi(G\times\overline{G})=\omega$; the construction uses two suitably chosen minimal Countryman lines. We also define a c.c.c. forcing of cardinality $\omega_1$ that adds a graph with the same properties. It remains open whether ZFC alone proves the existence of such a graph.