Sharp Dirac's theorem for DP-critical graphs

被引:21
作者
Bernshteyn, Anton [1 ]
Kostochka, Alexandr [1 ,2 ]
机构
[1] Univ Illinois, Dept Math, Champaign, IL 61820 USA
[2] Sobolev Inst Math, Novosibirsk 630090, Russia
基金
美国国家科学基金会; 俄罗斯基础研究基金会;
关键词
critical graphs; DP-coloring; list coloring; NUMBER; COLORINGS; EDGES;
D O I
10.1002/jgt.22227
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Correspondence coloring, or DP-coloring, is a generalization of list coloring introduced recently by Dvoak 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.
引用
收藏
页码:521 / 546
页数:26
相关论文
共 19 条
[1]   COLORINGS AND ORIENTATIONS OF GRAPHS [J].
ALON, N ;
TARSI, M .
COMBINATORICA, 1992, 12 (02) :125-134
[2]  
Alon N, 2000, RANDOM STRUCT ALGOR, V16, P364
[3]  
Bernshteyn A., 2017, DIFFERENCES DP COLOR
[4]  
Bernshteyn A., 2017, SIB MAT ZH, V58, P36
[5]   The asymptotic behavior of the correspondence chromatic number [J].
Bernshteyn, Anton .
DISCRETE MATHEMATICS, 2016, 339 (11) :2680-2692
[6]  
Bondy J.A., 2008, GTM
[7]   Colorings of plane graphs: A survey [J].
Borodin, O. V. .
DISCRETE MATHEMATICS, 2013, 313 (04) :517-539
[8]  
Borodin O. V., 1979, THESIS
[9]  
Dirac G. A., 1957, Proc. Lond. Math. Soc, Vs37, P161
[10]  
DIRAC GA, 1974, J REINE ANGEW MATH, V268, P150