Defective DP-colorings of sparse multigraphs

Yifan Jing, Alexandr Kostochka, Fuhong Ma, Pongpat Sittitrai, Jingwei Xu

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number103267
JournalEuropean Journal of Combinatorics
StatePublished - Mar 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Defective DP-colorings of sparse multigraphs'. Together they form a unique fingerprint.

Cite this