Defective DP-colorings of sparse simple graphs

Abstract

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 $g_{DP}(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 $g_{DP}(i,j,n)$ for each $i\ge 3$ and $j\ge 2i+1$ for infinitely many $n$.

17 pages

References in corpus (1)

• Defective DP-colorings of sparse multigraphs