Speaker: Claude Tardif (Royal Military College of Canada)
Dec. 02 2022
New counterexamples to Hedetniemi's conjecture
Abstract: I will describe an example showing that the chromatic number of the product of an 8-chromatic graph with a 5-chromatic graph can be 4. This is a new counterexample to the 1966 conjecture of Hedetniemi stating that the chromatic number of the product of two graphs is equal to the minimum of the chromatic numbers of the factors. I will explain why the conjecture remains interesting in my opinion.
[Slides]
