Counterexamples to the weak Hedetniemi Conjecture

Abstract

For any $n$, there exists finite simple graphs $G$ and $H$ such that $\chi (G),\chi (H)>n$ and $\chi (G\times H)=4$.

6 pages