Improved upper bound for feedback vertex sets in graphs of even degeneracy

Let kk be an even degeneracy bound, and let GG be an nn-vertex graph of degeneracy kk. Write ff for the size of a minimum feedback vertex set of GG.

There is an ε>0\varepsilon>0 such that

f(kk+2ε)n.f\leq \left(\frac{k}{k+2}-\varepsilon\right)n.

The paper gives an easy upper bound with coefficient kk+2\frac{k}{k+2} 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

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.