Xuding Zhu: Hedetniemi's conjecture and the Poljak-Rödl function

Abstract: Hedetniemi conjectured in 1966 that $\chi (G\times H)=min\left\{\chi \right(G),\chi (H\left)\right\}$ for all graphs $G,H$. This conjecture received a lot of attention in the past half century and was eventually refuted by Shitov in 2019. The Poljak-Rödl function is defined as $f\left(n\right)=min\left\{\chi \right(G\times H):\chi (G)=\chi (H)=n\}$. It is obvious that $f\left(n\right)\le n$ for all $n$, and Hedetniemi’s conjecture is equivalent to say that $f\left(n\right)=n$ for all integer $n$. Now we know that $f\left(n\right)<n$ for large $n$. However, we do not know how small $f\left(n\right)$ can be. In this talk, we will present new counterexamples to Hedetniemi's conjecture. We show that $f\left(n\right)\le (\frac{1}{2}+o(1\left)\right)n$ and survey some other work related to Hedetniemi’s conjecture.