On the DP-chromatic Number of Cartesian Products of Critical Graphs

Abstract

DP-coloring (also called correspondence coloring) is a well-studied generalization of list coloring introduced by Dvořák and Postle in 2015. The following sharp bound on the DP-chromatic number of the Cartesian product of graphs $G$ and $H$ is known: ${\chi }_{DP}(G\square H)\le \text{min}\{{\chi }_{DP}(G)+\text{col}(H),{\chi }_{DP}(H)+\text{col}(G)\}-1$ where ${\chi }_{DP}(G)$ is the DP-chromatic number of $G$ and $\text{col}(H)$ is the coloring number of $H$. We seek to understand when ${\chi }_{DP}(G\square K_{l,t})$ is far from its chromatic number: $\chi (G\square K_{l,t})=\max \{\chi (G),2\}$ in the case that $G$ is a $k$-critical graph with ${\chi }_{DP}(G)=k$. In particular, we have ${\chi }_{DP}(G\square K_{l,t})\le k+l$, and for fixed $l$ we wish to find the smallest $t$ for which this upper bound is achieved. This can be viewed as an extension of the classic result that the list chromatic number of $K_{l,t}$ is $l+1$ if and only if $t\ge l^l$. Our results illustrate that the DP color function of $G$, the DP analogue of the chromatic polynomial, provides a concept and tool that is useful for making progress on this problem.

15 pages, 4 figures