Covering planar graphs with forests

DOI10.1016/J.JCTB.2004.12.002MaRDI QIDQ1775897zbMATH OpenOpenAlexFDO

Authors József Balogh, Martin Kochol, András Pluhár, Xingxing Yu

Publication date 4 May 2005

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.2004.12.002

zbMATH Keywords

ForestsGraph minorsHamiltonian cyclesOuterplanar graphsPlanar graphsSeries parallel graphsTrees

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Covering planar graphs with forests, one having bounded maximum degree
• Covering planar graphs with forests, one having a bounded maximum degree
• Covering a graph by forests and a matching
• Edge covering pseudo-outerplanar graphs with forests
• Covering projective planar graphs with three forests
• Covering a graph with a constrained forest (extended abstract)
• scientific article; zbMATH DE number 1556750
• Covering paths and trees for planar grids
• On covering vertices of a graph by trees
• Uniform spanning forests of planar graphs

Cites work

• A Theorem on Planar Graphs
• Decomposition of Finite Graphs Into Forests
• Edge-Disjoint Spanning Trees of Finite Graphs
• Graph Classes: A Survey
• On the Problem of Decomposing a Graph into n Connected Factors
• Topology of series-parallel networks

Cited in

(43)

• Covering planar graphs with forests, one having bounded maximum degree
• Covering the edges of a graph by a prescribed tree with minimum overlap
• Decomposing 4-connected planar triangulations into two trees and one path
• Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices
• Heights of minor 5-stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 and 7
• Covering projective planar graphs with three forests
• Towards obtaining a 3-decomposition from a perfect matching
• Soft 3-stars in sparse plane graphs
• Caterpillar arboricity of planar graphs
• Low 5-stars in normal plane maps with minimum degree 5
• On the existence of specific stars in planar graphs
• 5-stars of low weight in normal plane maps with minimum degree 5
• Light 3-stars in sparse plane graphs
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Degree bounded forest covering
• Light and low 5-stars in normal plane maps with minimum degree 5
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Covering a graph with a constrained forest (extended abstract)
• Describing (d-2)-stars at d-vertices, d 5, in normal plane maps
• Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5
• Decomposition of sparse graphs into two forests, one having bounded maximum degree
• scientific article; zbMATH DE number 1953106 (Why is no real title available?)
• Edge covering pseudo-outerplanar graphs with forests
• scientific article; zbMATH DE number 1556750 (Why is no real title available?)
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Decomposing a graph into pseudoforests with one having bounded degree
• An introduction to the discharging method via graph coloring
• Low minor 5-stars in 3-polytopes with minimum degree 5 and no 6-vertices
• Algorithmic complexity of weakly semiregular partitioning and the representation number
• Covering planar graphs with forests, one having a bounded maximum degree
• scientific article; zbMATH DE number 7731183 (Why is no real title available?)
• Bounding clique size in squares of planar graphs
• On generalizations of pairwise compatibility graphs
• The complexity of decomposing a graph into a matching and a bounded linear forest
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• The arboricity of graphs with minimum genus embeddings
• Decomposing a graph into forests
• Covering planar graphs with a fixed number of balls
• Decomposing plane cubic graphs
• Low stars in normal plane maps with minimum degree 4 and no adjacent 4-vertices
• Decomposing a planar graph with girth 9 into a forest and a matching
• On covering vertices of a graph by trees
• Decomposition of sparse graphs, with application to game coloring number

This page was built for publication: Covering planar graphs with forests

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