
arXiv: 1703.02174
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 $��(G)$ is "close" to $n$, the DP-chromatic number of $G$ equals $��(G)$. "Close" here means $��(G)\geq 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
list coloring, Coloring of graphs and hypergraphs, DP-chromatic number, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
list coloring, Coloring of graphs and hypergraphs, DP-chromatic number, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
