Bounded diameter arboricity

Martin Merker, Luke Postle*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

79 Downloads (Pure)

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 languageEnglish
JournalJournal of Graph Theory
Number of pages13
ISSN0364-9024
DOIs
Publication statusPublished - 2018

Keywords

  • Arboricity
  • Bounded diameter
  • Ramsey density
  • Thin spanning trees

Fingerprint Dive into the research topics of 'Bounded diameter arboricity'. Together they form a unique fingerprint.

Cite this