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

DOI10.1016/J.IPL.2010.07.009zbMath1234.05190OpenAlexW2070466110MaRDI QIDQ407602

Xuding Zhu, Mickaël Montassier, Andre 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

decompositioncombinatorial problemsmaximum average degreemaddischarging procedureedge partitionforest with bounded degreeglobal rules

Mathematics Subject Classification ID

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

Cites Work

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

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