Max Lehr:
Counterexamples to Hedetniemi's Conjecture
Time and place
Monday, 26.2.24, 14:30-15:30, Raum 404, Ernst-Zermelo-Str. 1
Abstract
The tensor product \(G\btimes H\) of two finite graphs \(G\) and \(H\) is defined by \(V(G\btimes H) = V(G)\btimes V(H)\) and two vertices \((g_1,h_1)\) and \((g_2,h_2)\) being connected if \(g_1 E_G g_2\) and \(h_1 E_H h_2\). In 1966 Hedetniemi formulated the conjecture that \(\bchi(G\btimes H) = min(\bchi(G),\bchi(H))\). Only in 2019, more then 50 years later, Shitov discovered the existence of counterexamples. We will follow his proof and introduce some interesting notions along the way.