In 1912, Birkhoff, introduced the chromatic polynomial of a graph G that counts the number of proper colorings of G. List coloring, introduced in the 1970s by Erdos among others, is a natural generalization of ordinary coloring where each vertex has a restricted list of colors available to use on it. The list color function of a graph is a list coloring analogue of the chromatic polynomial that has been studied since its introduction by Kostochka and Sidorenko in 1990.
DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. Intuitively, DP-coloring is a variation on list coloring where each vertex in the graph still gets a list of colors, but identification of which colors are different can change from edge to edge. It is equivalent to the question of finding independent transversals in a (DP-)cover of a graph. In this talk, we will introduce a DP-coloring analogue of the chromatic polynomial called the DP color function, ask several fundamental open questions about it, and give an overview of the progress made on them. In particular, we will consider questions related to when the list-color function and the DP-color function equal the chromatic polynomial, including the solution of one such question of Thomassen (2009).
The results are based on joint work with Jeffrey Mudrock (CLC), as well as several groups of students (who will be introduced in the talk).
For Zoom information please contact Sean at SEnglish (at) illinois (dot) edu
