An analogue of DP-coloring for variable degeneracy and its applications
type: Item
instance of: scholarly article
title: An analogue of DP-coloring for variable degeneracy and its applications
zbMATH Open document ID: 1482.05121
author: Pongpat Sittitrai
author: Kittikorn Nakprasit
publication date: 2022-01-03T00:00:00Z
review text: ``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.
reviewed by: Carl Johan Casselgren
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7451242
zbMATH Keywords: DP-coloring
zbMATH Keywords: list arboricity
zbMATH Keywords: planar graph
zbMATH Keywords: list coloring
zbMATH Keywords: vertex arboricity
MaRDI profile type: Publication
full work available at URL: dmgt.2238
OpenAlex ID: W2973622759
cites work: The existence of unavoidable sets of geographically good configurations
cites work: On DP-coloring of graphs and multigraphs
cites work: Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
cites work: List 2-arboricity of planar graphs with no triangles at distance less than two
cites work: Planar graphs without triangular 4-cycles are 3-choosable
cites work: Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
cites work: Variable degeneracy: Extensions of Brooks' and Gallai's theorems
cites work: Vertex arboricity of planar graphs without intersecting 5-cycles
cites work: The point-arboricity of a graph
cites work: The Point-Arboricity of Planar Graphs
cites work: Vertex-arboricity of planar graphs without intersecting triangles
cites work: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
cites work: Q4198056
cites work: A Note on the Vertex Arboricity of a Graph
cites work: On the vertex-arboricity of planar graphs without 7-cycles
cites work: Vertex arboricity of planar graphs without chordal 6-cycles
cites work: A sufficient condition for DP-4-colorability
cites work: Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
cites work: On the vertex-arboricity of planar graphs
cites work: Every planar graph is 5-choosable
cites work: Q4135588
cites work: List colourings of planar graphs
cites work: Note on a paper of B. Grünbaum on acyclic colorings
cites work: LIST POINT ARBORICITY OF GRAPHS
Wikidata QID: Q127204306
DOI: 10.7151/DMGT.2238
Recommended article: On DP-coloring of graphs and multigraphs
Recommended article: Generalized DP-colorings of graphs
Recommended article: A note on a Brooks' type theorem for DP‐coloring
Recommended article: On Equitable Coloring of d-Degenerate Graphs
Recommended article: Colorings and homomorphisms of degenerate and bounded degree graphs
Recommended article: Degree‐bounded coloring of graphs: Variations on a theme by brooks
Recommended article: Equitable Colourings of d-degenerate Graphs
Recommended article: On DP‐coloring of digraphs
Recommended article: DP-colorings of hypergraphs
Recommended article: The \(d\)-precoloring problem for \(k\)-degenerate graphs
published in: Discussiones Mathematicae Graph Theory
description: scientific article; zbMATH DE number 7451242