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, W. Haken, The existence of unavoidable sets of geographically good configuration, Illinois J. Math. 20 (1976) 218–297.
- A. Bernshteyn, A. Kostochka and S. Pron, On DP-coloring of graphs and multigraphs, Sib. Math.l J. 58 (2017) 28–36.
- 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.
- 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.
- O.V. Borodin, A.O. Ivanova, Planar graphs without triangular $4$-cycles are $4$-choosable, Sib. Èlektron. Mat. Rep. 5 (2008) 75–79.
- 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.
- O.V. Borodin, A.V. Kostochka and B. Toft, Variable degeneracy: extensions of Brooks and Gallai's theorems, Discrete Math. 214 (2000) 101–112.
- H. Cai, J-L. Wu and L. Sun, Vertex arboricity of planar graphs without intersecting 5-cycles, J. Comb. Optim. 35 (2018) 365–372.
- G. Chartrand, H.V. Kronk and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169–175.
- G. Chartrand, H.V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612–616.
- M. Chen, A. Raspaud and W. Wang, Vertex-arboricity of planar graphs without intersecting triangles, European J. Combin. 33 (2012) 905–923.
- 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.
- 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).
- 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).
- S.L. Hakimi, E.F. Schmeichel, A note on the vertex arboricity of a graph, SIAM J. Discrete Math. 2 (1989) 64–67.
- D. Huang, W.C. Shiu and W. Wang, On the vertex-arboricity of planar graphs without 7-cycles, Discrete Math. 312 (2012) 2304–2315.
- D. Huang, W. Wang, Vertex arboricity of planar graphs without chordal 6-cycles, Int. J. Comput. Math. 90 (2013) 258–272.
- S.-J. Kim, K. Ozeki, A sufficient condition for DP-$4$-colorability, Discrete Math. 341 (2018) 1983–1986.
- S.-J. Kim, X. Yu, Planar graphs without $4$-cycles adjacent to triangles are DP-$4$-colorable, Graph and Combin. 35 (2019) 707–718.
- A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075.
- C. Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994) 180–181.
- 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.
- G. Wegner, Note on a paper by B. Grünbaum on acyclic colorings, Israel J. Math. 14 (1973) 409–412.
- N. Xue, B. Wu, List point arboricity of graphs, Discrete Math. Algorithms Appl 4(2) (2012) 1–10.
Close