{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:42:51Z","timestamp":1753893771182,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>We study the minimum size $f$ of a feedback vertex set in directed and undirected $n$-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\\frac{k-1}{k+1}n$ is known to be tight for graphs with bounded treewidth $k$ or bounded odd degeneracy $k$. We show that neither of the easy upper and lower bounds $\\frac{k-1}{k+1}n$ and $\\frac{k}{k+2}n$ can be exact for the case of even degeneracy. More precisely, for even degeneracy $k$ we prove that $f &lt; \\frac{k}{k+2}n$ and for every $\\epsilon&gt;0$, there exists a $k$-degenerate graph for which $f\\geq \\frac{3k-2}{3k+4}n -\\epsilon$.\r\nFor directed graphs of bounded degeneracy $k$, we prove that $f\\leq\\frac{k-1}{k+1}n$ and that this inequality is strict when $k$ is odd. For directed graphs of bounded treewidth $k\\geq 2$, we show that $f \\leq \\frac{k}{k+3}n$ and for every $\\epsilon&gt;0$, there exists a $k$-degenerate graph for which $f\\geq \\frac{k-2\\lfloor\\log_2(k)\\rfloor}{k+1}n -\\epsilon$. Further, we provide several constructions of low degeneracy or treewidth and large $f$.<\/jats:p>","DOI":"10.37236\/10914","type":"journal-article","created":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T08:25:23Z","timestamp":1666340723000},"source":"Crossref","is-referenced-by-count":0,"title":["Feedback Vertex Sets in (Directed) Graphs of Bounded Degeneracy or Treewidth"],"prefix":"10.37236","volume":"29","author":[{"given":"Kolja","family":"Knauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoang","family":"La","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petru","family":"Valicov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2022,10,21]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p16\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p16\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T08:25:24Z","timestamp":1666340724000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i4p16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,10,6]]}},"URL":"https:\/\/doi.org\/10.37236\/10914","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,10,21]]},"article-number":"P4.16"}}