On differences between DP-coloring and list coloring
A. Yu. Bernshteyna, A. V. Kostochkaab
a University of Illinois at Urbana-Champaign, Urbana, IL, USA
b Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia
DP-Coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle . Many known upper bounds for the list-chromatic number extend to the DP-chromatic number, but not all of them do. In this note we describe some properties of DP-coloring that set it aside from list coloring. In particular, we give an example of a planar bipartite graph with DP-chromatic number $4$ and prove that the edge-DP-chromatic number of a $d$-regular graph with $d\geq2$ is always at least $d+1$.
list coloring of a graph, edge coloring, DP-coloring of a graph.
|Russian Foundation for Basic Research
|National Science Foundation
|The work of the first author was partially supported by the Illinois Distinguished Fellowship. The work of the second author was partially supported by the Russian Foundation for Basic Research (projects 18-01-00353 and 16-01-00499) and by the National Science Foundation (project DMS-1600592).
PDF file (258 kB)
Siberian Advances in Mathematics, 2019, 29, 183–189
A. Yu. Bernshteyn, A. V. Kostochka, “On differences between DP-coloring and list coloring”, Mat. Tr., 21:2 (2018), 61–71; Siberian Adv. Math., 29 (2019), 183–189
Citation in format AMSBIB
\by A.~Yu.~Bernshteyn, A.~V.~Kostochka
\paper On differences between DP-coloring and list coloring
\jour Mat. Tr.
\jour Siberian Adv. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|