Mathematics Colloquium
Speaker: Hemanshu Kaul, Illinois Institute of Technology
Host: Niranjan Balachandran
Title: Counting Colorings: Variations and Extensions of a theme of Kostochka and Sidorenko
Time, day and date: 4:45:00 PM - 5:45:00 PM, Wednesday, September 30
Venue: Ramanujan Hall
Abstract: In 1990, Kostochka and Sidorenko introduced the List Color Function, which counts the guaranteed number of list colorings of a given graph, as a counterpart to the classic Chromatic Polynomial, introduced by Birkhoff in 1912, which counts its ordinary colorings. They asked whether the List Color Function asymptotically equals the Chromatic Polynomial when the number of colors is large enough. This was proved by Donner (1992) with several major improvements continuing to appear till now. This phenomenon has been widely studied in the context of generalizations of ordinary colorings.
In this talk, we will discuss the history as well as some new results on this theme of Kostochka and Sidorenko: an enumerative function of (a variant of) list colorings equals the corresponding enumerative function of (the same variant of) ordinary colorings, when the number of colors is large enough. We will also see when this phenomenon fails in context of DP-colorings but can still be recovered using the Tutte polynomial.