A Note on Hedetniemi's Conjecture, Stahl's Conjecture and the Poljak-Rödl Function

  • Claude Tardif
  • Xuding Zhu
DOI: https://doi.org/10.37236/8787

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) \leq 1/2 + \epsilon$ for large values of $\min\{\chi(G), \chi(H)\}$.

Published
2019-11-22
Issue
Volume 26, Issue 4 (2019)
Article Number
P4.32