The lower-bound conjecture for the induced-forest ratio

Let GG be a graph with minimum degree δ(G)2\delta(G)\geq 2. Define t(G)t(G) as the minimum size of a vertex set whose deletion leaves an induced forest, let LIF(G)\operatorname{LIF}(G) denote the maximum order of an induced forest in GG, and set

f(G)=LIF(G)t(G).f(G)=\frac{\operatorname{LIF}(G)}{t(G)}.

Lower-bound conjecture. If GG has minimum degree at least 22, then

f(G)2.f(G)\geq 2.

This conjecture is motivated by exhaustive computations for graphs of order at most 1010 and minimum degree at least 22, which support the proposed universal lower bound.

Sources & referencesView supporting material

Primary source

Saieed Akbari, Alireza Amanihamedani, Sepehr Mousavi, Hesam Nikpey and Soheil Sheybani, “On the Maximum Order of Induced Paths and Induced Forests in Regular Graphs”, arXiv:1911.02332 (2019).

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.