On the Chromatic Polynomial and Counting DP-Colorings

The chromatic polynomial of a graph has been studied since the early 20th century; it is a polynomial that outputs the number of proper m-colorings of the graph for any positive integer input m. List coloring is a well-known variation on classic vertex coloring where each vertex of a graph receives a list of available colors, and we seek to find a proper coloring of the graph such that the color used on each vertex of the graph comes from the list of colors corresponding to the vertex. In the early 1990’s a list analogue of the chromatic polynomial, called the list color function, was introduced. Many results in the literature comparing the list color function of a graph to its chromatic polynomial have appeared.

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. In this talk, we introduce the DP color function, a DP-coloring analogue of the chromatic polynomial that counts DP-colorings of a graph. Motivated by known results comparing the list color function and chromatic polynomial of graphs, we show that while the DP color function behaves similar to the list color function for some graphs, there are some surprising differences. This talk will be accessible to students familiar with the basics of graph theory.

This is joint work with Hemanshu Kaul.

Event Topic

Discrete Applied Math Seminar