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 $♢$, 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.

12 pages