Montassier et al.'s bounded-degree forest decomposition conjecture

About 16 years old · traced to

Let kk and dd be positive integers, and let GG be a graph. Write Υf(G)\Upsilon_f(G) for the fractional arboricity of GG, defined by

Υf(G)=max⁡H⊆G∣E(H)∣∣V(H)∣−1.\Upsilon_f(G)=\max_{H\subseteq G}\frac{|E(H)|}{|V(H)|-1}.

Montassier et al.'s conjecture. If

Υf(G)≤k+dk+d+1,\Upsilon_f(G)\leq k+\frac{d}{k+d+1},

then E(G)E(G) can be decomposed into k+1k+1 forests, one of which has maximum degree at most dd.

This conjecture generalizes the known decompositions of graphs with fractional arboricity at most 43\tfrac{4}{3} or 32\tfrac{3}{2}. It is open for k≥2k\geq 2 or d≥7d\geq 7.

References

Primary source

Tomas Kaiser, Mickael Montassier and Andre Raspaud, “Covering a graph by forests and a matching”, arXiv:1007.0316 (2010).

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.