TY - JOUR
T1 - Defective DP-colorings of sparse multigraphs
AU - Jing, Yifan
AU - Kostochka, Alexandr
AU - Ma, Fuhong
AU - Sittitrai, Pongpat
AU - Xu, Jingwei
N1 - A.K. was partially supported by NSF, USA grant DMS-1600592, by grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research and by Arnold O. Beckman Campus Research Board, USA Award RB20003 of the University of Illinois at Urbana–Champaign.J.X. was partially supported by Arnold O. Beckman Campus Research Board, USA Award RB20003 of the University of Illinois at Urbana-Champaign.
PY - 2021/3
Y1 - 2021/3
N2 - 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 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.
AB - 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 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.
UR - http://www.scopus.com/inward/record.url?scp=85097762196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097762196&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2020.103267
DO - 10.1016/j.ejc.2020.103267
M3 - Article
AN - SCOPUS:85097762196
SN - 0195-6698
VL - 93
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103267
ER -