On Differences Between DP-Coloring and List Coloring

A. Yu Bernshteyn, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review

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 ⩾ 2 is always at least d + 1.

Original languageEnglish (US)
Pages (from-to)183-189
Number of pages7
JournalSiberian Advances in Mathematics
Volume29
Issue number3
DOIs
StatePublished - Jul 1 2019

Keywords

  • DP-coloring of a graph
  • edge coloring
  • list coloring of a graph

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On Differences Between DP-Coloring and List Coloring'. Together they form a unique fingerprint.

Cite this