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

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)=maxHGE(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 k2k\geq 2 or d7d\geq 7.

Sources & referencesView supporting material

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.