Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

[摘要] We prove that for any c \geq 5, there exists an infinite family (G_n )_{n\in \mathbb{N}} of graphs such that 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.

[学科分类] 物理化学和理论化学

[关键词] categorical product;graph colouring;Hedetniemi's conjecture