1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Relaxed DP-Coloring and another Generalization of DP-Coloring on Planar Graphs without 4-Cycles and 7-Cycles

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 15 May 2020
Accepted: 18 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

DP-coloring is generalized via relaxed coloring and variable degeneracy in [P. Sittitrai and K. Nakprasit, Su cient 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

MSC 2010

[1] 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/S003744661701004910.1134/S0037446617010049Search in Google Scholar

[2] 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-610.1016/S0012-365X(99)00221-6Search in Google Scholar

[3] 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.00110.1016/j.jctb.2017.09.001Search in Google Scholar

[4] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. Inst. Combin. Appl. 25 (1999) 79–88.Search in Google Scholar

[5] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125–159.Search in Google Scholar

[6] 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-610.1016/S0893-9659(00)00147-6Search in Google Scholar

[7] 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-610.1007/s00373-020-02177-6Search in Google Scholar

[8] 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.223810.7151/dmgt.2238Search in Google Scholar

[9] P. Sittitrai and K. Nakprasit, Su cient 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-x10.1007/s00373-019-02038-xSearch in Google Scholar

[10] R.Škrekovski, List improper colourings of planar graphs, Combin. Probab. Comput. 8 (1999) 293–299. https://doi.org/10.1017/S096354839900375210.1017/S0963548399003752Search in Google Scholar

[11] V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3–10, in Russian.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo