Abstract
We introduce the notion ofbounded diameter arboricity.Specifically, thediameter‐darboricityof a graph is theminimum numberksuch that the edges of the graph canbe partitioned intokforests each of whose componentshas diameter at mostd. A class of graphs has boundeddiameter arboricitykif there exists a natural numberdsuch that every graph in the class has diameter‐darboricity at mostk. We conjecture that the class ofgraphs with arboricity at mostkhas bounded diameterarboricity at mostk+1. We prove this conjecture for∈k{2, 3}by proving the stronger assertion that theunion of a forest and a star forest can be partitioned intotwo forests of diameter at most 18. We use these results tocharacterize the bounded diameter arboricity for planargraphs of girth at leastgfor all≠g5.Asanapplicationwe show that every 6‐edge‐connected planar (multi)graphcontains two edge‐disjoint(18/19)‐thin spanning trees.Moreover, we answer a question by Mütze and Peter,leading to an improved lower bound on the density ofglobally sparse Ramsey graphs
Original language | English |
---|---|
Journal | Journal of Graph Theory |
Number of pages | 13 |
ISSN | 0364-9024 |
DOIs | |
Publication status | Published - 2018 |
Keywords
- Arboricity
- Bounded diameter
- Ramsey density
- Thin spanning trees