21
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
25
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .