Abstract :

In this talk we will go through the history of Hedetniemi's conjecture, a nearly 60 years old graph theory conjecture, which was refuted in the very recent years. In the category of graphs one can easily observe that the chromatic number of the meet, or the categorical product, of two graphs cannot be bigger than the minimum of the chromatic numbers of the factors. In the 1960's S. T. Hedetniemi conjectured that equality holds here as well. This conjecture was reformulated in 1985 using the notion of exponential graphs. Based on this reformulation, in 2019, Y. Shitov disproved the conjecture for very large chromatic numbers (about $2^{100}$). Later, in more recent years, counterexamples for smaller chromatic numbers were constructed by X. Zhu, C. Tardif and M. Wrochna, and in the end of 2022 the last open case was solved by Tardif. In the smaller constructions some special graphs, the universal graphs for wide colorings, were used. In this talk we will discuss the key ideas of some of the proofs and the role of this special graph family.