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

DOI10.1016/J.IPL.2010.07.009MaRDI QIDQ407602zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

combinatorial problemsdecompositiondischarging procedureedge partitionforest with bounded degreeglobal rulesmadmaximum average degree

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(7)

• Decompositions of graphs into forests with bounded maximum degree
• \(\{0, 2 \}\)-degree free spanning forests in graphs
• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• scientific article; zbMATH DE number 4008408 (Why is no real title available?)
• Decomposing a graph into pseudoforests with one having bounded degree
• Characterizing Sparse Graphs by Map Decompositions
• Decomposition of sparse graphs, with application to game coloring number

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)