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

## Description of video

 Date: 9/11/20 Speaker : Zhu Xuding

## Keywords

Abstract: Hedetniemi conjectured in 1966 that $\chi \left(G×H\right)=min\left\{\chi \left(G\right),\chi \left(H\right)\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 \left(G×H\right):\chi \left(G\right)=\chi \left(H\right)=n\right\}$. 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) 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 \left(\frac{1}{2}+o\left(1\right)\right)n$ and survey some other work related to Hedetniemi’s conjecture.

Ivanov Grigory

on 10/21/22

Keller Chaya

on 5/7/21

Girão António

on 12/9/22