On the chromatic polynomial and counting DP-colorings of graphs

The chromatic polynomial of a graph G, denoted P(G, m), is equal to the number of proper m-colorings of G. The list color function of graph G, denoted P-l(G, m), is a list analogue of the chromatic polynomial that has been studied since 1992, primarily through comparisons with the corresponding chromatic polynomial. DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvorak and Postle. In this paper, we introduce a DP-coloring analogue of the chromatic polynomial called the DP color function, denoted P-DP(G, m), and ask several fundamental open questions about it, making progress on some of them. Motivated by known results related to the list color function, we show that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences. For example, Wang, Qian, and Yan recently showed that if G is a connected graph with ledges, then P-l(G, m) = P(G, m) whenever m > l-1/ln(1+root 2), but we will show that for any g >= 3 there exists a graph, G, with girth g such that P-DP(G, m) < P(G, m) when m is sufficiently large. We also study the asymptotics of P(G, m) - P-DP(G, m) for a fixed graph G. We develop techniques to compute P-DP(G, m) exactly and apply them to certain classes of graphs such as chordal graphs, unicyclic graphs, and cycles with a chord. Finally, we make progress towards showing that for any graph G, there is a p such that P-DP(G boolean OR K-p, m) = P(G boolean OR K-p, m) for large enough m. (C) 2020 Elsevier Inc. All rights reserved.

Automated summary

In this paper, we introduce a DP-coloring analogue of the chromatic polynomial called the DP color function and ask several fundamental open questions about it. The study shows that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences. Additionally, the paper discusses the asymptotics of the difference between the fixed graph G's chromatic polynomial and DP-coloring.