DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle. We introduce and study (i,j)-defective DP-colorings of simple graphs. Let gDP(i,j,n) be the minimum number of edges in an n-vertex DP-(i,j)-critical graph. In this paper we determine sharp bound on gDP(i,j,n) for each i≥3 and j≥2i+1 for infinitely many n.
- Defective coloring
- List coloring
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics