Answers to two questions on the DP color function

Jeffrey A. Mudrock¹ ; Seth Thomason

¹College of Lake County

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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$.

Détail

DOI : 10.37236/9863

Classification : 05C15, 05C30, 05C69, 05C31
Mots-clés : DP-coloring, list coloring, chromatic polynomial