On Differences Between DP-Coloring and List Coloring
Anton Bernshteyn, Alexandr V. Kostochka · Siberian Advances in Mathematics · 2019
DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle [12]. 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 ⩾ 2 is always at least d + 1.