Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

DOI10.1002/jgt.21711zbMath1276.05092OpenAlexW1930792227MaRDI QIDQ2862551

Seog-Jin Kim, Xuding Zhu, Hehui Wu, Douglas B. West, Alexandr V. Kostochka

Publication date: 15 November 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21711

zbMATH Keywords

forestgraph decompositiondischargingfractional arboricitymaximum average degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Related Items (17)

Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ Decomposing 4-connected planar triangulations into two trees and one path ⋮ Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\) ⋮ Spanning Rigid Subgraph Packing and Sparse Subgraph Covering ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Digraph analogues for the Nine Dragon Tree Conjecture ⋮ Decomposing plane cubic graphs ⋮ The pseudoforest analogue for the strong nine dragon tree conjecture is true ⋮ Decomposing a graph into pseudoforests with one having bounded degree ⋮ Degree Bounded Forest Covering ⋮ Spanning tree with lower bound on the degrees ⋮ Decomposing a graph into forests and a matching ⋮ An enhancement of Nash-Williams' theorem on edge arboricity of graphs ⋮ Decomposing a planar graph with girth at least 8 into a forest and a matching ⋮ Decomposing a graph into forests: the nine dragon tree conjecture is true ⋮ Triangle decompositions of planar graphs ⋮ Decomposing a graph into forests

Cites Work

• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposing a graph into forests
• Decomposing a planar graph with girth 9 into a forest and a matching
• Decomposition of sparse graphs, with application to game coloring number
• Planar graphs decomposable into a forest and a matching
• Covering planar graphs with forests, one having bounded maximum degree
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• Covering planar graphs with forests
• Decomposing a planar graph into a forest and a subgraph of restricted maximum degree
• Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
• Edge-partitions of planar graphs and their game coloring numbers
• Decompositions of quadrangle-free planar graphs
• Decomposition of Finite Graphs Into Forests

This page was built for publication: Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree