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 language | English (US) |
---|---|
Pages (from-to) | 521-546 |
Number of pages | 26 |
Journal | Journal of Graph Theory |
Volume | 88 |
Issue number | 3 |
DOIs | |
State | Published - Jul 2018 |
Keywords
- DP-coloring
- critical graphs
- list coloring
ASJC Scopus subject areas
- Geometry and Topology