Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
Claude Tardif · Commentationes Mathematicae Universitatis Carolinae · 2023
We prove that for any $c \geq 5$, there exists an infinite family $(G_n )_{n\in \mathbb{N}}$ of graphs such that $\chi(G_n) > c$ for all $n\in \mathbb{N}$ and $\chi(G_m \times G_n) \leq c$ for all $m eq n$. These counterexamples to Hedetniemi's conjecture show that the Boolean lattice of exponential graphs with $K_c$ as a base is infinite for $c \geq 5$.