|
This article is cited in 14 scientific papers (total 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.
Received: 18.12.2017
Citation:
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
Linking options:
https://www.mathnet.ru/eng/mt338 https://www.mathnet.ru/eng/mt/v21/i2/p61
|
Statistics & downloads: |
Abstract page: | 308 | Full-text PDF : | 137 | References: | 42 | First page: | 5 |
|