RUS  ENG
Full version
JOURNALS // Matematicheskie Trudy // Archive

Mat. Tr., 2018 Volume 21, Number 2, Pages 61–71 (Mi mt338)

This article is cited in 14 papers

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

Abstract: 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\geq2$ is always at least $d+1$.

Key words: list coloring of a graph, edge coloring, DP-coloring of a graph.

UDC: 519.17

Received: 18.12.2017

DOI: 10.17377/mattrudy.2018.21.202


 English version:
Siberian Advances in Mathematics, 2019, 29, 183–189

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024