2019/12/07 by Jing, Yifan, Kostochka, Alexandr, Ma, Fuhong +2
#05C15 #05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1912.03421
DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvorak and Postle. We introduce and study (i,j)-defective DP-colorings of multigraphs. We concentrate on sparse multigraphs and consider fDP(i,j,n) --- the minimum number of edges that may have an n-vertex (i,j)-critical multigraph, that is, a multigraph G that has no (i,j)-defective DP-coloring but whose every proper subgraph has such a coloring. For every i and j, we find linear lower bounds on fDP(i,j,n) that are exact for infinitely many n.