Forest-and-bounded-diameter-forest decomposition conjecture

About 10 years old · traced to

Let d≥1d\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 d≤2d\leq2, with f(2)≤18f(2)\leq18, but the assertion for general dd 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.