An analogue of DP-coloring for variable degeneracy and its applications (Q2062675)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An analogue of DP-coloring for variable degeneracy and its applications |
scientific article |
Statements
An analogue of DP-coloring for variable degeneracy and its applications (English)
0 references
3 January 2022
0 references
``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. \textit{O. V. Borodin} and \textit{A. O. Ivanova} [J. Graph Theory 62, No. 3, 234--240 (2009; Zbl 1180.05035)] 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 so-called variable degeneracy. Inspired by these results and DP-coloring which is a generalization of list coloring and has become a widely studied topic'', the authors introduce a generalization of variable degeneracy; in particular, as a special case they generalize list vertex arboricity to so-called DP-vertex-arboricity. Using their generalization of variable degeneracy, they extend the aforementioned general result by Borodin and Ivanova [loc. cit.]. Furthermore, their main result also generalizes a result by \textit{S.-J. Kim} and \textit{X. Yu} [Graphs Comb. 35, No. 3, 707--718 (2019; Zbl 1416.05082)] which states that every planar graph without \(4\)-cycles adjacent to \(3\)-cycles is DP-4-colorable.
0 references
DP-coloring
0 references
list arboricity
0 references
planar graph
0 references
list coloring
0 references
vertex arboricity
0 references
0 references
0 references