Answers to Two Questions on the DP Color Function

Abstract

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)$. 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\to \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\ge 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$.

13 pages. arXiv admin note: text overlap with arXiv:1904.07697