Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Commentationes mathematicae Universitatis Carolinae

article

Claude Tardif

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

DOI  :  10.14712/1213-7243.2023.003

学科分类：物理化学和理论化学

来源: Univerzita Karlova v Praze * Matematicko-Fyzikalni Fakulta / Charles University in Prague, Faculty of Mathematics and Physics

【 摘 要 】

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.

【 授权许可】

CC BY