Bounded diameter arboricity

Research output: Research - peer-reviewJournal article – Annual report year: 2018


View graph of relations

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 languageEnglish
JournalJournal of Graph Theory
Number of pages13
StatePublished - 2018
CitationsWeb of Science® Times Cited: 0

    Research areas

  • Arboricity, Bounded diameter, Ramsey density, Thin spanning trees
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 159435036