Sparse critical graphs for defective DP-colorings

Alexandr Kostochka, Jingwei Xu

Research output: Contribution to journalArticlepeer-review

Abstract

An interesting generalization of list coloring is so called DP-coloring (named after Dvořák and Postle). We study (i,j)-defective DP-colorings of simple graphs. Define gDP(i,j,n) to be the minimum number of edges in an n-vertex DP-(i,j)-critical graph. We prove sharp bounds on gDP(i,j,n) for i=1,2 and j≥2i for infinitely many n.

Original languageEnglish (US)
Article number113899
JournalDiscrete Mathematics
Volume347
Issue number5
DOIs
StatePublished - May 2024

Keywords

  • DP-coloring
  • Defective coloring
  • List coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Sparse critical graphs for defective DP-colorings'. Together they form a unique fingerprint.

Cite this