Defective DP-colorings of sparse simple graphs

Yifan Jing, Alexandr Kostochka, Fuhong Ma, Jingwei Xu

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish (US)
Article number112637
JournalDiscrete Mathematics
Volume345
Issue number1
DOIs
StatePublished - Jan 2022

Keywords

  • DP-coloring
  • Defective coloring
  • List coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this