  Hedetniemi conjectured in 1966 that $\chi(G \times H) = \min\{\chi(G),
\chi(H)\}$ for any graphs G and H. Here $G\times H$ is the graph with vertex
set
  $ V(G)\times V(H)$ defined by putting $(x,y)$ and $(x',y')$ adjacent if and
only if
  $xx'\in E(G)$ and $yy'\in V(H)$. This conjecture received a lot of attention
in the past half century.
  It was disproved recently by Shitov.
  The Poljak-R\"{o}dl function is defined as $f(n) = \min\{\chi(G \times H):
\chi(G)=\chi(H)=n\}$.
  Hedetniemi's conjecture is equivalent to saying $f(n)=n$ for all integer $n$.
Shitov's result shows that
  $f(n)<n$ when $n$ is sufficiently large. Using Shitov's result, Tardif and
Zhu showed that $f(n) \le n - (\log n)^{1/4}$ for sufficiently large $n$. Using
Shitov's method, He--Wigderson showed that for $\epsilon \approx 10^{-9}$ and
$n$ sufficiently large, $f(n) \le (1-\epsilon)n$. In this note we prove that a
slight modification of the proof in the paper of Zhu and Tardif shows that
$f(n) \le (\frac 12 + o(1))n$ for sufficiently large $n$. On the other hand, it
is unknown whether $f(n)$ is bounded by a constant. However, we do know that if
$f(n)$ is bounded by a constant, then the smallest such constant is at most
$9$. This lecture note gives self-contained proofs of the above mentioned
results.
