Article in volume
Authors:
Title:
Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without $4$-cycles and $7$-cycles
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 287-297
Received: 2020-05-15 , Revised: 2021-03-18 , Accepted: 2021-03-18 , Available online: 2021-04-27 , https://doi.org/10.7151/dmgt.2405
Abstract:
DP-coloring is generalized via relaxed coloring and variable degeneracy in
[P. Sittitrai and K. Nakprasit, Sufficient conditions on planar
graphs to have a relaxed DP-$3$-coloring, Graphs Combin. 35 (2019) 837–845],
[K.M. Nakprasit and K. Nakprasit, A generalization of some results on list
coloring and DP-coloring, Graphs Combin. 36 (2020) 1189–1201] and
[P. Sittitrai and K. Nakprasit, An analogue of DP-coloring for variable
degeneracy and its applications, Discuss. Math. Graph Theory]. In this work,
we introduce another concept that includes two previous generalizations.
We demonstrate its application on planar graphs
without $4$-cycles and $7$-cycles. One implication is that the vertex set of
every planar graph without $4$-cycles and $7$-cycles can be partitioned into
three sets in which each of them induces a linear forest and one of them is
an independent set. Additionally, we show that every planar graph without
$4$-cycles and $7$-cycles is DP-$(1,1,1)$-colorable. This generalizes a result
of Lih et al. [A note on list improper coloring planar graphs,
Appl. Math. Lett. 14 (2001) 269–273] that every planar graph without
$4$-cycles and $7$-cycles is $(3,1)^*$-choosable.
Keywords:
relaxed DP-colorings, variable degeneracy, planar graphs, discharging
References:
- A.Yu. Bernshteyn, A.V. Kostochka and S.P. Pron, On DP-coloring of graphs and multigraphs, Sib. Math. J. 58 (2017) 28–36.
https://doi.org/10.1134/S0037446617010049 - O.V. Borodin, A.V. Kostochka and B. Toft, Variable degeneracy: extensions of Brooks and Gallai's theorems, Discrete Math. 214 (2000) 101–112.
https://doi.org/10.1016/S0012-365X(99)00221-6 - Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths $4$ to $8$, J. Combin. Theory Ser. B. 129 (2018) 38–54.
https://doi.org/10.1016/j.jctb.2017.09.001 - N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. Inst. Combin. Appl. 25 (1999) 79–88.
- P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125–159.
- K. Lih, Z. Song, W. Wang and K. Zhang, A note on list improper coloring planar graphs, Appl. Math. Lett. 14 (2001) 269–273.
https://doi.org/10.1016/S0893-9659(00)00147-6 - K.M. Nakprasit and K. Nakprasit, A generalization of some results on list coloring and DP-coloring, Graphs Combin. 36 (2020) 1189–1201.
https://doi.org/10.1007/s00373-020-02177-6 - P. Sittitrai and K. Nakprasit, An analogue of DP-coloring for variable degeneracy and its applications, Discuss. Math. Graph Theory, in press.
https://doi.org/10.7151/dmgt.2238 - P. Sittitrai and K. Nakprasit, Sufficient conditions on planar graphs to have a relaxed DP-$3$-coloring, Graphs Combin. 35 (2019) 837–845.
https://doi.org/10.1007/s00373-019-02038-x - R. Škrekovski, List improper colourings of planar graphs, Combin. Probab. Comput. 8 (1999) 293–299.
https://doi.org/10.1017/S0963548399003752 - V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3–10, in Russian.
Close