An Analogue of DP-Coloring for Variable Degeneracy and its Applications

Abstract

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
• 05c10
• 05c15