Claude Tardif
Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Comment.Math.Univ.Carolin. 63,3 (2022) 315-327.

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