Abstract: 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 \neq 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.
Keywords: categorical product; graph colouring; Hedetniemi's conjecture
DOI: DOI 10.14712/1213-7243.2023.003
AMS Subject Classification: 05C15