TY - JOUR
T1 - On 2-defective DP-colorings of sparse graphs
AU - Kostochka, Alexandr
AU - Xu, Jingwei
N1 - Publisher Copyright:
© 2020 Elsevier Ltd
PY - 2021/1
Y1 - 2021/1
N2 - Introduced by Dvořák and Postle, the notion of DP-coloring generalizes list coloring and helps to prove new results on list coloring. We consider 1-defective and 2-defective DP-colorings of graphs with 2 colors. For j=1,2, we find exact lower bounds on the number of edges in (j,2)-DP-critical graphs (that is, graphs that do not admit j-defective DP-colorings with 2 colors but whose every proper subgraph has such a coloring) with a given number of vertices. These bounds also hold for (j,2)-list-critical graphs, and for j=2 are better than previously known bounds by Havet and Sereni (2006).
AB - Introduced by Dvořák and Postle, the notion of DP-coloring generalizes list coloring and helps to prove new results on list coloring. We consider 1-defective and 2-defective DP-colorings of graphs with 2 colors. For j=1,2, we find exact lower bounds on the number of edges in (j,2)-DP-critical graphs (that is, graphs that do not admit j-defective DP-colorings with 2 colors but whose every proper subgraph has such a coloring) with a given number of vertices. These bounds also hold for (j,2)-list-critical graphs, and for j=2 are better than previously known bounds by Havet and Sereni (2006).
UR - http://www.scopus.com/inward/record.url?scp=85089823806&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089823806&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2020.103217
DO - 10.1016/j.ejc.2020.103217
M3 - Article
AN - SCOPUS:85089823806
SN - 0195-6698
VL - 91
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103217
ER -