Geodesic
An Analogue of DP-Coloring for Variable Degeneracy and its Applications
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 89-99.

Voir la notice de l'article provenant de la source Library of Science

A graph G is list vertex k-arborable if for every k-assignment L, one can choose f(v) ∈ L(v) for each vertex v so that vertices with the same color induce a forest. In [6], Borodin and Ivanova proved that every planar graph without 4-cycles adjacent to 3-cycles is list vertex 2-arborable. In fact, they proved a more general result in terms of variable degeneracy. Inspired by these results and DP-coloring which is a generalization of list coloring and has become a widely studied topic, we introduce a generalization on variable degeneracy including list vertex arboricity. We use this notion to extend a general result by Borodin and Ivanova. Not only this theorem implies results about planar graphs without 4-cycles adjacent to 3-cycle by Borodin and Ivanova, it also implies other results including a result by Kim and Yu [S.-J. Kim and X. Yu, Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, Graphs Combin. 35 (2019) 707–718] that every planar graph without 4-cycles adjacent to 3-cycles is DP-4-colorable.
Keywords: DP-colorings, arboricity colorings, planar graphs 
@article{DMGT_2022_42_1_a6,
     author = {Sittitrai, Pongpat and Nakprasit, Kittikorn},
     title = {An {Analogue} of {DP-Coloring} for {Variable} {Degeneracy} and its {Applications}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {89--99},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a6/}
}
TY  - JOUR
AU  - Sittitrai, Pongpat
AU  - Nakprasit, Kittikorn
TI  - An Analogue of DP-Coloring for Variable Degeneracy and its Applications
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 89
EP  - 99
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a6/
LA  - en
ID  - DMGT_2022_42_1_a6
ER  - 
%0 Journal Article
%A Sittitrai, Pongpat
%A Nakprasit, Kittikorn
%T An Analogue of DP-Coloring for Variable Degeneracy and its Applications
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 89-99
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a6/
%G en
%F DMGT_2022_42_1_a6
Sittitrai, Pongpat; Nakprasit, Kittikorn. An Analogue of DP-Coloring for Variable Degeneracy and its Applications. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 89-99. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a6/

[1] K. Appel and W. Haken, The existence of unavoidable sets of geographically good configuration, Illinois J. Math. 20 (1976) 218–297. https://doi.org/10.1215/ijm/1256049898

[2] A. Bernshteyn, A. Kostochka and S. Pron, On DP-coloring of graphs and multi-graphs, Sib. Math. J. 58 (2017) 28–36. https://doi.org/10.1134/S0037446617010049

[3] O.V. Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3 -colorings, J. Graph Theory 21 (1996) 183–186. https://doi.org/10.1002/(SICI)1097-0118(199602)21:2¡183::AID-JGT7¿3.0.CO;2-N

[4] O.V. Borodin and A.O. Ivanova, List 2 -arboricity of planar graphs with no triangles at distance less than two, Sib. Èlektron. Mat. Izv. 5 (2008) 211–214.

[5] O.V. Borodin and A.O. Ivanova, Planar graphs without triangular 4 -cycles are 3- choosable, Sib.Èlektron. Mat. Izv. 5 (2008) 75–79.

[6] O.V. Borodin and A.O. Ivanova, Planar graphs without 4 -cycles adjacent to 3 -cycles are list vertex 2 -arborable, J. Graph Theory 62 (2009) 234–240. https://doi.org/10.1002/jgt.20394

[7] 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

[8] H. Cai, J-L. Wu and L. Sun, Vertex arboricity of planar graphs without intersecting 5 -cycles, J. Comb. Optim. 35 (2018) 365–372. https://doi.org/10.1007/s10878-017-0168-3

[9] G. Chartrand, H.V. Kronk and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169–175. https://doi.org/10.1007/BF02760181

[10] G. Chartrand and H.V. Kronk, The point-arboricity of planar graphs, J. Lond. Math. Soc. (2) 44 (1969) 612–616. https://doi.org/10.1112/jlms/s1-44.1.612

[11] M. Chen, A. Raspaud and W. Wang, Vertex-arboricity of planar graphs without intersecting triangles, European J. Combin. 33 (2012) 905–923. https://doi.org/10.1016/j.ejc.2011.09.017

[12] 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

[13] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proceedings, West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, CA, Congr. Numer. 26 (1979) 125–157.

[14] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, New York, 1979).

[15] S.L. Hakimi and E.F. Schmeichel, A note on the vertex arboricity of a graph, SIAM J. Discrete Math. 2 (1989) 64–67. https://doi.org/10.1137/0402007

[16] D. Huang, W.C. Shiu and W. Wang, On the vertex-arboricity of planar graphs without 7 -cycles, Discrete Math. 312 (2012) 2304–2315. https://doi.org/10.1016/j.disc.2012.03.035

[17] D. Huang and W. Wang, Vertex arboricity of planar graphs without chordal 6 -cycles, Int. J. Comput. Math. 90 (2013) 258–272. https://doi.org/10.1080/00207160.2012.727989

[18] S.-J. Kim and K. Ozeki, A sufficient condition for DP- 4 -colorability, Discrete Math. 341 (2018) 1983–1986. https://doi.org/10.1016/j.disc.2018.03.027

[19] S.-J. Kim and X. Yu, Planar graphs without 4 -cycles adjacent to triangles are DP- 4 -colorable, Graphs Combin. 35 (2019) 707–718. https://doi.org/10.1007/s00373-019-02028-z

[20] A. Raspaud and W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075. https://doi.org/10.1016/j.ejc.2007.11.022

[21] C. Thomassen, Every planar graph is 5 -choosable, J. Combin. Theory Ser. B 62 (1994) 180–181. https://doi.org/10.1006/jctb.1994.1062

[22] V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3–10.

[23] M. Voigt, List colourings of planar graphs, Discrete Math. 120 (1993) 215–219. https://doi.org/10.1016/0012-365X(93)90579-I

[24] G. Wegner, Note on a paper by B. Grünbaum on acyclic colorings, Israel J. Math. 14 (1973) 409–412. https://doi.org/10.1007/BF02764717

[25] N. Xue and B. Wu, List point arboricity of graphs, Discrete Math. Algorithms Appl. 4 (2012) 1–10. https://doi.org/10.1142/51793830912500279