On DP-coloring of graphs and multigraphs

Abstract

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): v ∈ V (G) and c ∈ 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□K_k, but DP-coloring seems more promising and useful than the Plesnevič–Vizing reduction. Some properties of the DP-chromatic number χ_DP (G) resemble the properties of the list chromatic number χ_l(G) but some differ quite a lot. It is always the case that χ_DP (G) ≥ χ_l(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.