Line graph

Discrete mathematics

Chromatic scale

Brooks' theorem

Graph

Mathematics

List coloring

Fractional coloring

Combinatorics

Graph power

1-planar graph

Chromatic polynomial

Chordal graph

Graph coloring

Advances in Applied Mathematics

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ℓ(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 Dvořák and Postle. In this paper, we introduce a DP-coloring analogue of the chromatic polynomial called the DP color function, denoted PDP(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 l edges, then Pℓ(G,m)=P(G,m) whenever m>l−1ln⁡(1+2), but we will show that for any g≥3 there exists a graph, G, with girth g such that PDP(G,m)<P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m)−PDP(G,m) for a fixed graph G. We develop techniques to compute PDP(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 PDP(G∨Kp,m)=P(G∨Kp,m) for large enough m.

On the chromatic polynomial and counting DP-colorings of graphs