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)
- Asymptotically good edge correspondence colouring
- Cover and variable degeneracy
- Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
- A Sufficient condition for DP-4-colorability
- Variable degeneracy on toroidal graphs
- DP-3-coloring of some planar graphs
- A note on a Brooks' type theorem for DP-coloring
- A refinement of choosability of graphs
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
- Every planar graph without adjacent cycles of length at most is -choosable
- Partial DP-Coloring
- DP color functions versus chromatic polynomials
- On the Chromatic Polynomial and Counting DP-Colorings
- is upperly bounded by