Chromatic polynomial and counting DP-colorings of graphs : Problems and progress

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 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. We show that while the DP color function behaves similar to the list color function and chromatic polynomial for some graphs, there are also some surprising fundamental differences.

The results are based on joint work with Jeffrey Mudrock (CLC), as well as several groups of students