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).
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics