Hedetniemi conjectured in 1966 that $chi(G times H) = min{chi(G), chi(H)}$ for all graphs $G$ and $H$. Here $Gtimes 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 $xxin E(G)$ and $yyin 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)$. Shitovs proof shows that Hedetniemis 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 $3lceil 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 Hedetniemis conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
Download