ÀÏÍõÂÛ̳

Speaker: Hemanshu Kaul, associate professor of applied mathematics, Illinois Institute of Technology

Title: Counting List Colorings: Two new perspectives on a theme of Kostochka and Sidorenko

Abstract:
In 1990, Kostochka and Sidorenko introduced the List Color Function, \(P_\ell(G,k)\) which is the guaranteed number of list colorings of a labeled graph \(G\) over all \(k\)-list assignments of \(G\). They asked whether \(P_\ell(G,k)\) equals \(P(G,k)\), the chromatic polynomial, when \(k\) is large enough. This was proved by Donner (1992) with further major improvements by Thomassen (2009), Wang, Qian, and Yan (2017),  Dong and Zhang (2023) on the threshold on \(k\) that gives this equality. This phenomenon has been widely studied in the context of both list colorings and DP-colorings, including extremal questions about the threshold on \(k\) (many of which remain open).

In this talk, we discuss 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) classical colorings, when the number of colors is large enough.

We discuss how this phenomenon arises:

• When counting the number of list packings in a graph (list packing asks for the existence of multiple pairwise disjoint list colorings of the graph). Here the corresponding classical coloring enumeration is related to counting a generalization of Latin arrays. This generalizes the work on list color function listed above.
• When counting list colorings of unlabeled graphs (recall that chromatic polynomial and other enumerative functions mentioned above all assume the given grpah is labeled). This is inspired by, and generalizes, the seminal work of Hanlon (1985) on the study of chromatic polynomial of unlabeled graphs.

This is joint work with Jeff Mudrock (U. of South Alabama).

Discrete Applied Math Seminar