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.
References
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
No solutions have been posted yet.