Bounded diameter arboricity plus-one conjecture
Bounded diameter arboricity plus-one conjecture
Let be a finite simple graph, let denote its arboricity, and let denote the bounded diameter arboricity of a graph class . For , write for the class of graphs with arboricity at most .
Bounded diameter arboricity plus-one conjecture. The class has bounded diameter arboricity , that is,
The conjecture asks whether allowing one more forest always suffices to partition the edges of every graph of arboricity at most into forests with uniformly bounded component diameters. The paper proves it for , while the general case remains open.
Sources & referencesView supporting material
Primary source
Martin Merker and Luke Postle, “Bounded Diameter Arboricity”, arXiv:1608.05352 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.