DP‐coloring Cartesian products of graphs.

DP‐coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. Motivated by results related to list coloring Cartesian products of graphs, we initiate the study of the DP‐chromatic number, χDP ${\chi }_{DP}$, of the same. We show that χDP(G□H)≤min{χDP(G)+col(H),χDP(H)+col(G)}−1 ${\chi }_{DP}(G\,\square \,H)\le \,\text{min}\,\{{\chi }_{DP}(G)\,+\text{col}(H),{\chi }_{DP}(H)+\text{col}\,(G)\}-1$, where col(H) $\,\text{col}\,(H)$ is the coloring number of the graph H $H$. We focus on building tools for lower bound arguments for χDP(G□H) ${\chi }_{DP}(G\,\,\square \,\,H)$ and use them to show the sharpness of the bound above and its various forms. Our results illustrate that the DP‐color function of G $G$, the DP analogue of the chromatic polynomial, is essential in the study of the DP‐chromatic number of the Cartesian product of graphs, including the following question that extends the sharpness problem above and the classical result on gap between list‐chromatic number and chromatic number: given any graph G $G$ and k∈N $k\in {\mathbb{N}}$, what is the smallest t $t$ for which χDP(G□Kk,t)=χDP(G)+k ${\chi }_{DP}(G\,\square \,{K}_{k,t})={\chi }_{DP}(G)+k$? [ABSTRACT FROM AUTHOR]

Copyright of Journal of Graph Theory is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)