A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function

Abstract

We prove that $\min \{\chi (G),\chi (H)\}-\chi (G\times H)$ can be arbitrarily large, and that if Stahl's conjecture on the multichromatic number of Kneser graphs holds, then $\min \{\chi (G),\chi (H)\}/\chi (G\times H)\le 1/2+\epsilon$ for large values of $\min \{\chi (G),\chi (H)\}$.

5 pages