Bounded diameter arboricity plus-one conjecture

About 10 years old · traced to

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 k≥1k\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.

References

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.