Bounded diameter arboricity |
| |
Authors: | Martin Merker Luke Postle |
| |
Institution: | 1. Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark;2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
Abstract: | We introduce the notion of bounded diameter arboricity. Specifically, the diameter- arboricity of a graph is the minimum number such that the edges of the graph can be partitioned into forests each of whose components has diameter at most . A class of graphs has bounded diameter arboricity if there exists a natural number such that every graph in the class has diameter- arboricity at most . We conjecture that the class of graphs with arboricity at most has bounded diameter arboricity at most . We prove this conjecture for 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 for all . As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint -thin spanning trees. Moreover, we answer a question by Mütze and Peter, leading to an improved lower bound on the density of globally sparse Ramsey graphs. |
| |
Keywords: | arboricity bounded diameter Ramsey density thin spanning trees |
|
|