Bounded diameter arboricity plus-one conjecture

Let GG be a finite simple graph, let Υ(G)\Upsilon(G) denote its arboricity, and let Υbd(G)\Upsilon_{bd}(\mathcal{G}) denote the bounded diameter arboricity of a graph class G\mathcal{G}. For k1k\geq 1, write Ak\mathcal{A}_k for the class of graphs with arboricity at most kk.

Bounded diameter arboricity plus-one conjecture. The class Ak\mathcal{A}_k has bounded diameter arboricity k+1k+1, that is,

Υbd(Ak)=k+1.\Upsilon_{bd}(\mathcal{A}_k)=k+1.

The conjecture asks whether allowing one more forest always suffices to partition the edges of every graph of arboricity at most kk into forests with uniformly bounded component diameters. The paper proves it for k{2,3}k\in\{2,3\}, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.