On Differences Between DP-Coloring and List Coloring

By Anton Bernshteyn, Alexandr V. Kostochka. Siberian Advances in Mathematics, 2017

48 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/2af9d35c3219245524219299cffab0ee01012c12