JournalsjemsVol. 19, No. 1pp. 285–298

Hedetniemi's conjecture for uncountable graphs

  • Assaf Rinot

    Bar-Ilan University, Ramat Gan, Israel
Hedetniemi's conjecture for uncountable graphs cover
Download PDF

A subscription is required to access this article.

Abstract

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

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

Cite this article

Assaf Rinot, Hedetniemi's conjecture for uncountable graphs. J. Eur. Math. Soc. 19 (2017), no. 1, pp. 285–298

DOI 10.4171/JEMS/666