#paper #graphs #coloring_graphs #countably_chromatic # Abstract It is proved that in Gödel’s constructible universe, for every infinite successor cardinal κ, there exist graphs G and H of size and chromatic number κ, for which the product graph G × H is countably chromatic. # Introduction **Def.** Given graphs $G_0 = (G_0 , E_0 )$ and $G_1 = (G_1 , E_1 )$, the product graph $G_0 ×G_1$ is defined as $(G_0 × G_1 , E_0 ∗ E_1 )$, where: • $G_0 × G_1 := {(g , h ) | g ∈ G_0 , h ∈ G_1 }$; • $E_0 ∗ E_1 := \{\{(g_0 , g_1 ), (g'_0 , g'_1 )\} | (g_0 , g'_0 ) ∈ E_0 \land (g_1 , g'_1 ) ∈ E_1 \}$. Clearly, a chromatic κ-coloring of one of the two graphs induces a chromatic κ-coloring of their product, and hence $Chr(G_0 ×G_1 ) ≤ min\{Chr(G_0 ), Chr(G_1)\}$ **Hedetniemi’s Conjecture ([Hed66]).** For all finite graphs $G_0$ and $G_1$ , $Chr(G_0 ×G_1 ) = min\{Chr(G_0 ), Chr(G_1)\}$ **The Weak Hedetniemi Conjecture ([Tar08]).** For every positive integer $k$, there exists a positive integer $ϕ(k)$, such that if $Chr(G_0 ) = Chr(G_1 ) = ϕ(k)$, then $Chr(G_0 × G_1 ) ≥ k$. **Failure of infinite Hedetniemi's conjecture - Hajnal** For every infinite cardinal $\lambda$ there exist graphs $G_0$ , $G_1$ such that: • $Chr(G_0 ) = Chr(G_1 ) = λ^+$; • $Chr(G_0 × G_1 ) = \lambda$ . **The Infiniwe Weak Hedetniemi Conjecture.** For every infinite cardinal $\kappa$, there exists a cardinal $ϕ(\kappa)$, such that if $Chr(G_0 ) = Chr(G_1 ) = ϕ(\kappa)$, then $Chr(G_0 × G_1 ) ≥ \kappa$. **Main Result.** If $λ$ is an uncountable cardinal, and diamond-in-square $λ$ holds, then there exist graphs $G_0$ , $G_1$ of size $λ^+$ such that: • $Chr(G_0 ) = Chr(G_1 ) = λ^+$; • $Chr(G_0 × G_1 ) = ℵ_0$ . **Corollary 1.** In Gödel’s constructible universe, GCH holds and all instances of the Infinite Weak Hedetniemi Conjecture fail. Indeed, for every infinite cardinals $λ ≥ κ$, there exist graphs $G_0$ , $G_1$ such that: • $Chr(G_0 ) = Chr(G_1 ) > λ$; • $Chr(G_0 × G_1 ) = \kappa$ . **Corollary 2.** If there exist class many strongly-compact cardinals, then the Infinite Weak Hedetniemi Conjecture holds.