Speaker: Xuding Zhu (Zhejiang Normal University)
Title: Hedetniemi's conjecture and Poljak-Rodl function
Time: 2020-12-03 (Thu.)  15:30 -16:30
Place: Auditorium, 6 Floor, Institute of Mathematics (NTU Campus)
Abstract: Hedetniemi conjectured in 1966 that for any graphs $G, H$, $\chi(G \times H) = \min\{\chi(G), \chi(H)\}$. This conjecture received a lot of attention in the past half century, and was refuted in 2019 by Shitov. The counterexample graphs constructed by Shitov have huge chromatic number ( $> 3^{90}$). Recently, I constructed counterexample graphs with chromatic number 125, and later Tardif improved it to 13. The Poljak-Rodl function is defined as $f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}$. Hedetniemi's conjecture is equivalent to say that $f(n)=n$ for all integer $n$. Shitov's result shows that for sufficiently large $n$, $f(n) < n$. A natural question is as how small can be $f(n)$. Recently, I proved that $f(n) \le (\frac 12 + o(1))n$. In this talk, I shall discuss ideas used in the constructions of these counterexamples of Hedetnimei's conjecture, problems and results motivated by the study of this conjecture.
  || Close window ||