On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree

DOI10.1016/j.amc.2018.01.003zbMath1426.05114OpenAlexW2793792375MaRDI QIDQ2423361

Weiqiang Yu, Min Chen, Wei Fan Wang

Publication date: 21 June 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2018.01.003

zbMATH Keywords

girthforestvertex partitionmaximum average degree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph designs and isomorphic decomposition (05C51)

Related Items

Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5

Cites Work

• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Globally sparse vertex‐ramsey graphs
• Unnamed Item