A Note on the Poljak-Rödl Function
Abstract
The Poljak-Rödl function is defined as $f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}$. This note proves that $\lim_{n \to \infty} \frac{f(n)}{n} \le \frac 12$.
The Poljak-Rödl function is defined as $f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}$. This note proves that $\lim_{n \to \infty} \frac{f(n)}{n} \le \frac 12$.