# Smallest known counterexamples to Hedetniemi’s conjecture

In 2019, Shitov has shown a counterexample (Ann. Math, 190(2) (2019) pp. 663-667) to Hedetniemi’s conjecture,

$$\chi(G \times H)=\min(\chi(G),\chi(H))$$ where $$\chi(G)$$ is the chromatic number of the undirected finite graph $$G$$.

Shitov counterexample is estimated to have $$|V(G)|\approx4^{100}$$ and $$|V(H)|\approx4^{10000}$$. Has there been some effort or progress to reduce the size of the counterexample?

## 1 Answer

Yes, Xuding Zhu did this in Relatively small counterexamples to Hedetniemi's conjecture (J. Comb. Theory B 146 (2021) pp. 141-150, doi:10.1016/j.jctb.2020.09.005, arXiv:2004.09028) where the sizes of the graphs are $$3403$$ and $$10501$$.

Marcin Wrochna has a preprint, Smaller counterexamples to Hedetniemi's conjecture, arXiv:2012.13558, that brings the sizes down to $$4686$$ and $$30$$ (as well as the chromatic number down to $$5$$).