Answers to Two Questions on the DP Color Function

  • Jeffrey A. Mudrock
  • Seth Thomason


DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvořák and Postle.  The chromatic polynomial of a graph is a notion that has been extensively studied since the early 20th century.  The chromatic polynomial of graph $G$ is denoted $P(G,m)$, and it is equal to the number of proper $m$-colorings of $G$.  In 2019, Kaul and Mudrock introduced an analogue of the chromatic polynomial for DP-coloring; specifically, the DP color function of graph $G$ is denoted $P_{DP}(G,m)$.  For vertex disjoint graphs $G$ and $H$, suppose $G \vee H$ denotes the join of $G$ and $H$.  Two fundamental questions posed by Kaul and Mudrock are: (1) For any graph $G$ with $n$ vertices, is it the case that $P(G,m)-P_{DP}(G,m) = O(m^{n-3})$ as $m \rightarrow \infty$? and (2) For every graph $G$, does there exist $p,N \in \mathbb{N}$ such that $P_{DP}(K_p \vee G, m) = P(K_p \vee G, m)$ whenever $m \geq N$?  We show that the answer to both these questions is yes.  In fact, we show the answer to (2) is yes even if we require $p=1$.

Article Number