$Z_{DP}(n)$ is upperly bounded by $n^2-(n+3)/2$

Abstract

DP-coloring was introduced by Dvořák and Postle and is a generalization of proper coloring. For any graph $G$, let $\chi (G)$ and ${\chi }_{DP}(G)$ denote the chromatic number and the DP-chromatic number of $G$ respectively. In this article, we show that ${\chi }_{DP}(G\vee K_s)=\chi (G\vee K_s)$ holds for $s=\lceil \frac{4(k+1)m}{2k+1}\rceil \le \lceil 2.4m\rceil$, where $k=\chi (G)$, $m=|E(G)|$ and $G\vee K_s$ is the join of $G$ and the complete graph $K_s$. Hence $Z_{DP}(n)\le n^2-(n+3)/2$ holds for every integer $n\ge 2$, where $Z_{DP}(n)$ is the minimum natural number $s$ such that ${\chi }_{DP}(G\vee K_s)=\chi (G\vee K_s)$ holds for every graph $G$ of order $n$. Our result improves the best current upper bound $Z_{DP}(n)\le 1.5n^2$ due to Bernshteyn, Kostochka and Zhu.

18 pages, 5 figures