*Meiqiao Zhang (National Institute of Education, Nanyang Technological University)
Fengming Dong (National Institute of Education, Nanyang Technological University)
DP coloring was introduced by Dvo\v{r}\'{a}k and Postle in 2015 to solve a problem in the field of list coloring. Broadly speaking, DP coloring is a generalization of both proper coloring and list coloring, which takes all possible compatible or exclusive relationships between the colors used on every pair of adjacent vertices into consideration. One of the main research topics in this area is to identify the commonalities and differences among proper coloring, list coloring and DP coloring. In this paper, we focus on the gap between the chromatic number $\chi(G)$ and the DP-chromatic number $\chi_{DP}(G)$ of any graph $G$.
Motivated by known results on the gap between chromatic numbers and list-chromatic numbers, Bernshteyn, Kostochka and Zhu defined $Z_{DP}(n)$ as the minimum natural number $s$ such that $\chi(G\vee K_s)=\chi_{DP}(G\vee K_s)$ holds for every graph $G$ of order $n$, where $G\vee K_s$ is the join of $G$ and the complete graph with $s$ vertices. They showed that $Z_{DP}(n)\le 1.5n^2$, which indicates that the join of any graph and a large enough complete graph has its chromatic number and DP-chromatic number equal. In this paper, we improve this best current upper bound into $n^2-(n+3)/2$, narrowing the gap between proper coloring and DP coloring to our knowledge.