A Generalization of Some Results on List Coloring and DP-Coloring

被引:5
作者
Nakprasit, Keaitsuda Maneeruk [1 ]
Nakprasit, Kittikorn [1 ]
机构
[1] Khon Kaen Univ, Fac Sci, Dept Math, Khon Kaen 40002, Thailand
关键词
DP-coloring; List coloring; Variable degeneracy; Vertex partition; Planar graph; PLANAR GRAPHS; VERTEX-ARBORICITY; POINT-ARBORICITY; TRIANGLES; 4-CYCLES; LENGTHS; CYCLES;
D O I
10.1007/s00373-020-02177-6
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph and let f(i), i is an element of {1, ... , s}, be a function from V(G) to the set of nonnegative integers. In Sittitrai and Nakprasit (Analogue of DP-coloring on variable degeneracy and its applications, 2020), the concept of DP-F-coloring, a generalization of DP-coloring and variable degeneracy, was introduced. We use DP-F-coloring to define DPG-[k, t]-colorable graphs and modify the proofs in Liu et al. (Graphs Combin 35(3), 695-705, 2019), Sittitrai and Nakprasit (Bull Malays Math Sci Soc, 2019, https://doi.org/10.1007/s40840-019-00800-1), Thomassen (J Combin Theory Ser B 62, 180-181, 1994) to obtain more results on list coloring, DP-coloring, list-forested coloring, and variable degeneracy.
引用
收藏
页码:1189 / 1201
页数:13
相关论文
共 29 条
  • [1] COLORINGS AND ORIENTATIONS OF GRAPHS
    ALON, N
    TARSI, M
    [J]. COMBINATORICA, 1992, 12 (02) : 125 - 134
  • [2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [3] EXISTENCE OF UNAVOIDABLE SETS OF GEOGRAPHICALLY GOOD CONFIGURATIONS
    APPEL, K
    HAKEN, W
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1976, 20 (02) : 218 - 297
  • [4] Bernshteyn A., ARXIV170504883
  • [5] ON DP-COLORING OF GRAPHS AND MULTIGRAPHS
    Bernshteyn, A. Yu.
    Kostochka, A. V.
    Pron, S. P.
    [J]. SIBERIAN MATHEMATICAL JOURNAL, 2017, 58 (01) : 28 - 36
  • [6] Borodin OV, 2008, SIB ELECTRON MATH RE, V5, P211
  • [7] Borodin OV, 2008, SIB ELECTRON MATH RE, V5, P75
  • [8] Planar Graphs Without 4-Cycles Adjacent to 3-Cycles Are List Vertex 2-Arborable
    Borodin, Oleg V.
    Ivanova, Anna O.
    [J]. JOURNAL OF GRAPH THEORY, 2009, 62 (03) : 234 - 240
  • [9] Variable degeneracy: extensions of Brooks' and Gallai's theorems
    Borodin, OV
    Kostochka, AV
    Toft, B
    [J]. DISCRETE MATHEMATICS, 2000, 214 (1-3) : 101 - 112
  • [10] Vertex arboricity of planar graphs without intersecting 5-cycles
    Cai, Hua
    Wu, Jianliang
    Sun, Lin
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) : 365 - 372