On DP-coloring of graphs and multigraphs

A. Yu Bernshteyn, A. V. Kostochka, S. P. Pron

Research output: Contribution to journalArticlepeer-review


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□Kk, 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.

Original languageEnglish (US)
Pages (from-to)28-36
Number of pages9
JournalSiberian Mathematical Journal
Issue number1
StatePublished - Jan 1 2017


  • critical graphs
  • list coloring
  • vertex degrees

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'On DP-coloring of graphs and multigraphs'. Together they form a unique fingerprint.

Cite this