On DP-coloring of graphs and multigraphs

Abstract

While solving a question on list coloring of planar graphs, Dvořák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph $G$ reduces the problem of finding a coloring of $G$ from a given list $L$ to the problem of finding a "large" independent set in an auxiliary graph $H(G,L)$ with vertex set $\{(v,c):v\in V(G)\text{ and }c\in L(v)\}$. It is similar to the old reduction by Plesnevič and Vizing of the $k$-coloring problem to the problem of finding an independent set of size $|V(G)|$ in the Cartesian product $G\square K_k$. Some properties of the DP-chromatic number ${\chi }_{DP}(G)$ resemble the properties of the list chromatic number ${\chi }_{\ell }(G)$ but some differ quite a lot. It is always the case that ${\chi }_{DP}(G)\ge {\chi }_{\ell }(G)$. The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erdős, Rubin, and Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai's Theorem on the minimum number of edges in $n$-vertex graphs critical with respect to DP-coloring.

12 pages, 1 figure