DP-colorings of graphs with high chromatic number

Anton Bernshteyn, Alexandr Kostochka, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

Abstract

DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle (2015). We prove that for every n-vertex graph G whose chromatic number χ(G) is “close” to n, the DP-chromatic number of G equals χ(G). “Close” here means χ(G)≥n−O(n), and we also show that this lower bound is best possible (up to the constant factor in front of n), in contrast to the case of list coloring.

Original languageEnglish (US)
Pages (from-to)122-129
Number of pages8
JournalEuropean Journal of Combinatorics
Volume65
DOIs
StatePublished - Oct 2017

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'DP-colorings of graphs with high chromatic number'. Together they form a unique fingerprint.

Cite this