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?


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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.