Decomposition of sparse graphs into two forests, one having bounded maximum degree

DOI10.1016/J.IPL.2010.07.009zbMATH Open1234.05190OpenAlexW2070466110MaRDI QIDQ407602FDOQ407602

Xuding Zhu, Mickaël Montassier, André Raspaud

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.07.009

Recommendations

• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• Decomposition of sparse graphs, with application to game coloring number
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• scientific article; zbMATH DE number 4008408
• Covering planar graphs with forests, one having bounded maximum degree

zbMATH Keywords

decompositioncombinatorial problemsmaximum average degreedischarging procedureedge partitionforest with bounded degreeglobal rulesmad

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Decomposition of Finite Graphs Into Forests
• Oriented 5-coloring of sparse plane graphs
• Covering planar graphs with forests, one having bounded maximum degree
• Covering planar graphs with forests
• The game coloring number of planar graphs
• Improper choosability of graphs and maximum average degree
• Edge-partitions of planar graphs and their game coloring numbers
• Decomposing a planar graph with girth 9 into a forest and a matching
• Decomposition of sparse graphs, with application to game coloring number
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Title not available (Why is that?)
• Circular \((5,2)\)-coloring of sparse graphs

Cited In (5)

• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• \(\{0, 2 \}\)-degree free spanning forests in graphs
• Characterizing Sparse Graphs by Map Decompositions
• Decompositions of graphs into forests with bounded maximum degree
• Title not available (Why is that?)

This page was built for publication: Decomposition of sparse graphs into two forests, one having bounded maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407602)