Bounded diameter arboricity

DOI10.1002/JGT.22416MaRDI QIDQ4632026zbMATH OpenOpenAlexWikidataFDO

Authors Martin Merker, Luke Postle

Publication date 25 April 2019

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

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

zbMATH Keywords

arboricitybounded diameterRamsey densitythin spanning trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ramsey theory (05D10)

Abstract: We introduce the notion of emph{bounded diameter arboricity}. Specifically, the emph{diameter-$d$ arboricity} of a graph is the minimum number $k$ such that the edges of the graph can be partitioned into $k$ forests each of whose components has diameter at most $d$. A class of graphs has bounded diameter arboricity $k$ if there exists a natural number $d$ such that every graph in the class has diameter-$d$ arboricity at most $k$. We conjecture that the class of graphs with arboricity at most $k$ has bounded diameter arboricity at most $k+1$. We prove this conjecture for $kin2,3$ by proving the stronger assertion that the union of a forest and a star forest can be partitioned into two forests of diameter at most 18. We use these results to characterize the bounded diameter arboricity for planar graphs of girth at least $g$ for all $ge5$. As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint $frac1819$-thin spanning trees.

Recommendations

• Thin trees in 8-edge-connected planar graphs
• On the vertex arboricity of planar graphs of diameter two
• scientific article; zbMATH DE number 19193
• Generalized arboricity of graphs with large girth
• On the vertex-arboricity of \(K_5\)-minor-free graphs of diameter 2

Cited in

(4)

• Thin trees in 8-edge-connected planar graphs
• Generalized arboricity of graphs with large girth
• Planar Ramsey graphs
• Beyond the pseudoforest strong nine dragon tree theorem

This page was built for publication: Bounded diameter arboricity

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