Hedetniemi's conjecture for uncountable graphs (Q509108)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hedetniemi's conjecture for uncountable graphs |
scientific article |
Statements
Hedetniemi's conjecture for uncountable graphs (English)
0 references
8 February 2017
0 references
Summary: 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 \textit{A. Hajnal} [Combinatorica 5, 137--139 (1985; Zbl 0575.05029)].
0 references
Hedetniemi's conjecture
0 references
product graph
0 references
almost countably chromatic
0 references
incompactness
0 references
constructible universe
0 references
Ostaszewski square
0 references
0 references
