Covering a graph by forests and a matching

DOI10.1137/100818340MaRDI QIDQ3225156zbMATH OpenOpenAlexFDO

Authors Tomáš Kaiser, Mickaël Montassier, André Raspaud

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.0316

zbMATH Keywords

decompositionforestfractional arboricitymatching

Mathematics Subject Classification ID

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

Abstract: We prove that for any positive integer $k$, the edges of any graph whose fractional arboricity is at most $k+1/(3k+2)$ can be decomposed into $k$ forests and a matching.

Recommendations

• Decomposing a graph into forests and a matching
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Decomposing a graph into forests
• Decomposition of sparse graphs into forests and a graph with bounded degree

Cited in

(11)

• Decomposing 4-connected planar triangulations into two trees and one path
• Decomposing a graph into forests and a matching
• Covering planar graphs with forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Degree bounded forest covering
• scientific article; zbMATH DE number 5952201 (Why is no real title available?)
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• scientific article; zbMATH DE number 1953106 (Why is no real title available?)
• scientific article; zbMATH DE number 1556750 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Decomposing a graph into forests

This page was built for publication: Covering a graph by forests and a matching

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