Fractional arboricity bounded-diameter conjecture

Let GG be a graph, let k1k\geq1 be a natural number, and let ε>0\varepsilon>0 be real. Write Υf(G)\Upsilon_f(G) for the fractional arboricity and Υd(G)\Upsilon_d(G) for the minimum number of forests whose components all have diameter at most dd.

Fractional arboricity bounded-diameter conjecture. There exists d(k,ε)d(k,\varepsilon) such that, if

Υf(G)kε,\Upsilon_f(G)\leq k-\varepsilon,

then

Υd(k,ε)(G)k.\Upsilon_{d(k,\varepsilon)}(G)\leq k.

This is proposed as a strong bounded-diameter consequence of fractional arboricity being separated from the integer arboricity threshold. The paper presents it as an additional open conjecture.

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.