## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 28-36 |

Number of pages | 9 |

Journal | Siberian Mathematical Journal |

Volume | 58 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2017 |

## Keywords

- critical graphs
- list coloring
- vertex degrees

## ASJC Scopus subject areas

- General Mathematics