A Note on the DP-Chromatic Number of Complete Bipartite Graphs

Abstract

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvořák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{\ell }(G)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}(G)$. On the other hand, there are several properties of the DP-chromatic number that shows that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{\ell }(K_{k,t})=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}(K_{k,t})=k+1$ if $t\ge 1+(k^k/k!)(\log (k!)+1)$, and we show that ${\chi }_{DP}(K_{k,t})<k+1$ if $t<k^k/k!$.

arXiv comment6 pages