Sharp Dirac's Theorem for DP-Critical Graphs

Abstract

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

arXiv comment26 pages, 1 figure

References in corpus (1)

• The asymptotic behavior of the correspondence chromatic number

Cited by in corpus (10)

• Asymptotically good edge correspondence colouring
• A Sufficient condition for DP-4-colorability
• Variable degeneracy on toroidal graphs
• DP-3-coloring of some planar graphs
• A note on a Brooks' type theorem for DP-coloring
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• On the Chromatic Polynomial and Counting DP-Colorings
• Every planar graph without adjacent cycles of length at most $8$ is $3$-choosable
• Partial DP-Coloring