Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.ejc.2017.05.007 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Graph,Complete coloring,Combinatorics,Chromatic scale,Upper and lower bounds,Vertex (graph theory),List coloring,Mathematics | Journal | 65 |
Issue | ISSN | Citations |
C | 0195-6698 | 3 |
PageRank | References | Authors |
0.42 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anton Bernshteyn | 1 | 21 | 3.37 |
Alexandr V. Kostochka | 2 | 682 | 89.87 |
Xuding Zhu | 3 | 1883 | 190.19 |