Improved upper bound for feedback vertex sets in graphs of even degeneracy
Improved upper bound for feedback vertex sets in graphs of even degeneracy
Let be an even degeneracy bound, and let be an -vertex graph of degeneracy . Write for the size of a minimum feedback vertex set of .
There is an such that
The paper gives an easy upper bound with coefficient and constructs non-trivial lower bounds, but does not essentially improve this upper bound; the conjecture asserts that a uniform improvement is possible.
Sources & referencesView supporting material
Primary source
Kolja Knauer, Hoang La and Petru Valicov, “Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth”, arXiv:2111.14986 (2022).
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.