Defective DP-colorings of sparse simple graphs

被引：4

作者：

Jing, Yifan ^{[1
]}

Kostochka, Alexandr ^{[1
,2
]}

Ma, Fuhong ^{[3
]}

Xu, Jingwei ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Sobolev Inst Math, Novosibirsk 630090, Russia

[3] Univ Sci & Technol China, Sch Math Sci, Hefei 230026, Peoples R China

来源：

DISCRETE MATHEMATICS | 2022年 / 345卷 / 01期

基金：

美国国家科学基金会; 中国国家自然科学基金; 俄罗斯基础研究基金会;

关键词：

Defective coloring; List coloring; DP-coloring; LIST IMPROPER COLORINGS; VERTEX DECOMPOSITIONS; MAXIMUM DEGREE; PLANAR GRAPHS; CHOOSABILITY; SUBGRAPH; GIRTH; (K;

D O I：

10.1016/j.disc.2021.112637

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvorak and Postle. We introduce and study (i, j)-defective DP-colorings of simple graphs. Let gDP(i, j, n) be the minimum number of edges in an n-vertex DP-(i, j)-critical graph. In this paper we determine sharp bound on g(DP)(i, j, n) for each i >= 3 and j >= 2i + 1 for infinitely many n. (c) 2021 Elsevier B.V. All rights reserved.

引用

页数：14

共 30 条

[1] A NOTE ON DEFECTIVE COLORINGS OF GRAPHS IN SURFACES [J].