DP-colorings of graphs with high chromatic number

Abstract

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

9 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 $8$ is $3$-choosable
• Partial DP-Coloring
• DP color functions versus chromatic polynomials
• On the Chromatic Polynomial and Counting DP-Colorings
• $Z_{DP}(n)$ is upperly bounded by $n^2-(n+3)/2$