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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics