DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

P. Sittitrai

Pongpat Sittitrai

Department of Mathematics, Faculty of Science
Khon Kaen University
Khon Kaen, 40002, Thailand

email: pongpat.sittitrai@gmail.com

K. Nakprasit

Kittikorn Nakprasit

Department of Mathematics, Faculty of Science
Khon Kaen University
Khon Kaen, 40002, Thailand

email: kitnak@hotmail.com

Title:

An analogue of DP-coloring for variable degeneracy and its applications

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 89-99

Received: 2018-08-22 , Revised: 2019-06-12 , Accepted: 2019-07-30 , Available online: 2019-09-20 , https://doi.org/10.7151/dmgt.2238

Abstract:

A graph $G$ is list vertex $k$-arborable if for every $k$-assignment $L,$ one can choose $f(v)\in 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

References:

  1. K. Appel, W. Haken, The existence of unavoidable sets of geographically good configuration, Illinois J. Math. 20 (1976) 218–297.
  2. A. Bernshteyn, A. Kostochka and S. Pron, On DP-coloring of graphs and multigraphs, Sib. Math.l J. 58 (2017) 28–36.
  3. O. V. Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. of Graph Theory 21 (1996) 183–186.
  4. O. V. Borodin, A. O. Ivanova, List 2-arboricity of planar graphs with no triangles at distance less than two, Sib. Elektron. Mat. Izv. 5 (2008) 211–214.
  5. O.V. Borodin, A.O. Ivanova, Planar graphs without triangular $4$-cycles are $4$-choosable, Sib. Èlektron. Mat. Rep. 5 (2008) 75–79.
  6. O.V. Borodin, A.O. Ivanova, Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable, J. Graph Theory 62 (2009) 234–240.
  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.
  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.
  9. G. Chartrand, H.V. Kronk and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169–175.
  10. G. Chartrand, H.V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612–616.
  11. M. Chen, A. Raspaud and W. Wang, Vertex-arboricity of planar graphs without intersecting triangles, European J. Combin. 33 (2012) 905–923.
  12. Z. Dvořák , L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths $4$ to $8$, J. Comb. Theory, Ser. B. 129 (2017) 38-54.
  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., Sept. 5-7, in: Congr. Numer. Vol.26, 1979).
  14. M.R. Garey, 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, E.F. Schmeichel, A note on the vertex arboricity of a graph, SIAM J. Discrete Math. 2 (1989) 64–67.
  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.
  17. D. Huang, W. Wang, Vertex arboricity of planar graphs without chordal 6-cycles, Int. J. Comput. Math. 90 (2013) 258–272.
  18. S.-J. Kim, K. Ozeki, A sufficient condition for DP-$4$-colorability, Discrete Math. 341 (2018) 1983–1986.
  19. S.-J. Kim, X. Yu, Planar graphs without $4$-cycles adjacent to triangles are DP-$4$-colorable, Graph and Combin. 35 (2019) 707–718.
  20. A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075.
  21. C. Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994) 180–181.
  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.
  24. G. Wegner, Note on a paper by B. Grünbaum on acyclic colorings, Israel J. Math. 14 (1973) 409–412.
  25. N. Xue, B. Wu, List point arboricity of graphs, Discrete Math. Algorithms Appl 4(2) (2012) 1–10.
Close