Forest-and-bounded-diameter-forest decomposition conjecture

Let d1d\geq1 be a natural number, and let GG be a graph that is the union of a forest and a second forest whose components have diameter at most dd.

Forest-and-bounded-diameter-forest decomposition conjecture. There exists a natural number f(d)f(d) such that GG can be partitioned into two forests, each of whose components has diameter at most f(d)f(d).

This conjecture generalizes the paper's forest-and-star-forest result. The paper confirms it when d2d\leq2, with f(2)18f(2)\leq18, but the assertion for general dd 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.