Decomposing a graph into forests

DOI10.1016/J.JCTB.2011.04.001zbMath1237.05167OpenAlexW2090015399WikidataQ60060266 ScholiaQ60060266MaRDI QIDQ765188

Mickaël Montassier, Xuding Zhu, Patrice Ossona de Mendez, Andre Raspaud

Publication date: 19 March 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2011.04.001

zbMATH Keywords

decompositionmatchinggirthplanar graphforestsfractional arboricitymaximum average degree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (20)

Extensions of matroid covering and packing ⋮ 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 planar graphs into graphs with degree restrictions ⋮ Decomposing plane cubic graphs ⋮ On the game coloring index of \(F^+\)-decomposable graphs ⋮ The pseudoforest analogue for the strong nine dragon tree conjecture is true ⋮ Thin trees in 8-edge-connected planar graphs ⋮ Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph ⋮ Generalized arboricity of graphs with large girth ⋮ Decomposing a graph into pseudoforests with one having bounded degree ⋮ The coloring game on planar graphs with large girth, by a result on sparse cactuses ⋮ Decomposing a graph into forests and a matching ⋮ An enhancement of Nash-Williams' theorem on edge arboricity of graphs ⋮ The incidence game chromatic number of \((a,d)\)-decomposable graphs ⋮ Decomposing a graph into forests: the nine dragon tree conjecture is true ⋮ Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• 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
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• Fractional arboricity, strength, and principal partitions in graphs and matroids
• The game coloring number of planar graphs
• Covering planar graphs with forests
• Refined activation strategy for the marking game
• Decomposing a planar graph into a forest and a subgraph of restricted maximum degree
• On the degrees of the vertices of a directed graph
• Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Edge-partitions of planar graphs and their game coloring numbers
• Decomposition of Finite Graphs Into Forests

This page was built for publication: Decomposing a graph into forests