paper

DP-colorings of graphs with high chromatic number

arXiv:1703.02174 · doi:10.1016/j.ejc.2017.05.007

Abstract

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

arXiv comment9 pages; v2: incorporated referees' comments

Cited by in corpus (15)