On 2-defective DP-colorings of sparse graphs

Alexandr Kostochka, Jingwei Xu

Research output: Contribution to journalArticlepeer-review

Abstract

Introduced by Dvořák and Postle, the notion of DP-coloring generalizes list coloring and helps to prove new results on list coloring. We consider 1-defective and 2-defective DP-colorings of graphs with 2 colors. For j=1,2, we find exact lower bounds on the number of edges in (j,2)-DP-critical graphs (that is, graphs that do not admit j-defective DP-colorings with 2 colors but whose every proper subgraph has such a coloring) with a given number of vertices. These bounds also hold for (j,2)-list-critical graphs, and for j=2 are better than previously known bounds by Havet and Sereni (2006).

Original languageEnglish (US)
Article number103217
JournalEuropean Journal of Combinatorics
Volume91
DOIs
StatePublished - Jan 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On 2-defective DP-colorings of sparse graphs'. Together they form a unique fingerprint.

Cite this