Journal of the European Mathematical Society


Full-Text PDF (196 KB) | Metadata | Table of Contents | JEMS summary
Volume 19, Issue 1, 2017, pp. 285–298
DOI: 10.4171/JEMS/666

Hedetniemi's conjecture for uncountable graphs

Assaf Rinot[1]

(1) Bar-Ilan University, Ramat Gan, Israel

It is proved that in Gödel's constructible universe, for every infinite successor cardinal $\kappa$, there exist graphs $\mathcal G$ and $\mathcal H$ of size and chromatic number $\kappa$, for which the product graph $\mathcal G \times \mathcal H$ is countably chromatic.

In particular, this provides an affirmative answer to a question of Hajnal from 1985.

Keywords: Hedetniemi's conjecture, product graph, almost countably chromatic, incompactness, constructible universe, Ostaszewski square

Rinot Assaf: Hedetniemi's conjecture for uncountable graphs. J. Eur. Math. Soc. 19 (2017), 285-298. doi: 10.4171/JEMS/666