On DP-coloring of graphs and multigraphs
By Anton Bernshteyn, Alexandr V. Kostochka, Sergei Pron. Siberian mathematical journal, 2016
81 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/543d256e16c141619740356478ffcb936613a99b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
Citations in the corpus
- On Differences Between DP-Coloring and List Coloring (2017, background): “One can extend the notion of DP-coloring to loopless multigraphs, see [6].”