Sharp Dirac's theorem for DP-critical graphs

Anton Bernshteyn, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review

Abstract

Correspondence coloring, or DP-coloring, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP-colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list-critical graphs that satisfy Dirac's bound with equality.

Original languageEnglish (US)
Pages (from-to)521-546
Number of pages26
JournalJournal of Graph Theory
Volume88
Issue number3
DOIs
StatePublished - Jul 2018

Keywords

  • DP-coloring
  • critical graphs
  • list coloring

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Sharp Dirac's theorem for DP-critical graphs'. Together they form a unique fingerprint.

Cite this