论文标题
对Hedetniemi的猜想相对较小的反例
Relatively small counterexamples to Hedetniemi's conjecture
论文作者
论文摘要
Hedetniemi在1966年猜想，所有图形$ g $和$ h $χ（g \ times h）= \ min \ {χ（g），χ（H）\} $。这里$ g \ times h $是带有顶点套装$ v（g）\ times v（h）$的图形，当时$（x，y）$和$（x'，y'）$相邻，并且仅当e（g）$ in（g）$和$ yy'\ in E（h）$中。在过去的半个世纪中，这个猜想引起了很多关注。 最近，Shitov驳斥了这一猜想。 令$ p $为奇数$ 7 $的最小顶点，而分数色度大于$ 3+4/（p-1）$。 Shitov的证明表明，Hedetniemi的猜想因某些图表而失败，其色度约为$ p^22^{p+1} $，并且大约$（p^22^{p+1}）^{p^32^{p-1}}} $ Vertices。在本文中，我们表明，猜想已经失败了某些图$ g $和$ h $，带有色数$ 3 \ lceil \ frac {p+1} 2 \ rceil $以及$ p \ lceil（p-1）/2 \ rceil $和$ 3 \ lceil $ and $ 3 \ lceil \ frac \ frac {p+1} 2 \ rceiL（目前以$ p $的上限为$ 148 $。因此，Hedetniemi的猜想因某些图表$ g $和$ h $而失败，$ g $，$ 225 $，分别为$ 10,952 $和$ 33,377 $的顶点。
Hedetniemi conjectured in 1966 that $χ(G \times H) = \min\{χ(G), χ(H)\}$ for all graphs $G$ and $H$. Here $G\times H$ is the graph with vertex set $ V(G)\times V(H)$ defined by putting $(x,y)$ and $(x',y')$ adjacent if and only if $xx'\in E(G)$ and $yy'\in E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitov's proof shows that Hedetniemi's conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3\lceil \frac {p+1}2 \rceil $ and with $p \lceil (p-1)/2 \rceil$ and $3 \lceil \frac {p+1}2 \rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemi's conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
