Fractional arboricity bounded-diameter conjecture

About 10 years old · traced to

Let GG be a graph, let k≥1k\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.

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.