

















Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant $δ>0$ such that for all $c$ sufficiently large, there exist graphs $G$ and $H$ with chromatic number at least $(1+δ)c$ for which $χ(G \times H) \le c$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。