期刊论文详细信息
Commentationes mathematicae Universitatis Carolinae | |
Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices | |
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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202307080003539ZK.pdf | 52KB | download |