Article in volume
Authors:
Title:
An analogue of DP-coloring for variable degeneracy and its applications
PDFSource:
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:
- 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 - A. Bernshteyn, A. Kostochka and S. Pron, On DP-coloring of graphs and multigraphs, Sib. Math. J. 58 (2017) 28–36.
https://doi.org/10.1134/S0037446617010049 - 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 - 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.
- O.V. Borodin and A.O. Ivanova, Planar graphs without triangular $4$-cycles are $3$-choosable, Sib. Èlektron. Mat. Izv. 5 (2008) 75–79.
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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.
- 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).
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3–10.
- M. Voigt, List colourings of planar graphs, Discrete Math. 120 (1993) 215–219.
https://doi.org/10.1016/0012-365X(93)90579-I - 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 - N. Xue and B. Wu, List point arboricity of graphs, Discrete Math. Algorithms Appl. 4 (2012) 1–10.
https://doi.org/10.1142/51793830912500279
Close