On DP-coloring of graphs and multigraphs

While solving a question on the 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 the auxiliary graph $H(G,L)$ with vertex set $\{(v,c)\colon 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$, but DP-coloring seems more promising and useful than the Plesnevič–Vizing reduction. Some properties of the DP-chromatic number $\chi_\mathrm{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_\mathrm{DP}(G)\geq\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–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.