Journal article
Bounded diameter arboricity
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
Language: | English |
---|---|
Year: | 2018 |
Pages: | 629-641 |
ISSN: | 10970118 and 03649024 |
Types: | Journal article |
DOI: | 10.1002/jgt.22416 |
ORCIDs: | Merker, Martin and 0000-0002-5023-269X |