Description
Abstract:
Hedetniemi conjectured in 1966 that $\chi(G \times H) = \min\{\chi(G), \chi(H)\}$ 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\"{o}dl function is defined as $f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}$. It is obvious that $f(n) \le n$ for all $n$, and Hedetniemi's conjecture is equivalent to saying that $f(n)=n$ for all integer $n$. Now we know that $f(n) < n$ for large $n$. However, we do not know how small $f(n)$ can be. In this talk, we will present new counterexamples to Hedetniemi's conjecture. We show that $f(n) \le (\frac 12 + o(1))n$ and survey some other works related to the subject.
The Zoom link is:
https://zoom.us/j/92691482350?pwd=eDNlVHVHRzJIbWxuelV3SHpIMGtLZz09
Meeting ID: 926 9148 2350
Passcode: 112358