论文标题
Hedetniemi猜想的较小的反例
Smaller counterexamples to Hedetniemi's conjecture
论文作者
论文摘要
Hedetniemi的猜想〜\ cite {hedetniemi1966 Homormormorphisms}对于$ c $ - 颜色指出，张量$ g \ times h $是$ c $ -c $ colororable可在$ g $或$ g $或$ g $ is $ g $ is $ g $ is $ c $ c $ -c $ -co $ -cobolorable时。 El-Zahar和Sauer〜 \ cite {el-Zahars85}以$ C = 3 $证明了这一点。 在最近的突破中，Shitov〜 \ cite {shitov19}显示了大型$ c $的反例。 尽管Shitov的证明已经非常短，但Zhu \ cite {Zhu20}简化了该参数，并给出了$ C = 125 $的更明确的反例。 tardif \ cite {tardif20}表明，对参数的修改允许使用``宽颜色''以$ c = 14 $而获得反例，而$ c = 13 $，更多涉及词典术品。本说明提出了另外两个小修改，导致$ c = 5 $的反例（分别为$ g $和$ h $，分别为4686和30个顶点）。
Hedetniemi's conjecture~\cite{hedetniemi1966homomorphisms} for $c$-colorings states that the tensor product $G \times H$ is $c$-colorable if and only if $G$ or $H$ is $c$-colorable. El-Zahar and Sauer~\cite{El-ZaharS85} proved it for $c = 3$. In a recent breakthrough, Shitov~\cite{Shitov19} showed counterexamples, for large $c$. While Shitov's proof is already remarkably short, Zhu \cite{Zhu20} simplified the argument and gave a more explicit counterexample for $c=125$. Tardif \cite{Tardif20} showed that a modification of the arguments allows to use ``wide colorings'' to obtain counterexamples for $c=14$, and $c=13$ with a more involved use of lexicographic products. This note presents two more small modifications, resulting in counterexamples for $c=5$ (with $G$ and $H$ having 4686 and 30 vertices, respectively).
