The lower-bound conjecture for the induced-forest ratio
The lower-bound conjecture for the induced-forest ratio
Let be a graph with minimum degree . Define as the minimum size of a vertex set whose deletion leaves an induced forest, let denote the maximum order of an induced forest in , and set
Lower-bound conjecture. If has minimum degree at least , then
This conjecture is motivated by exhaustive computations for graphs of order at most and minimum degree at least , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.