{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:52Z","timestamp":1771036372303,"version":"3.50.1"},"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>Given a nonnegative integer $d$ and a graph $G$,\u00a0let $f_d(G)$ be the maximum order\u00a0of an induced forest in $G$ having maximum degree at most $d$.\u00a0We seek lower bounds for $f_d(G)$ based on the order and treewidth of $G$.We show that, for all $k,d\\ge 2$ and $n\\ge 1$,\u00a0if $G$ is a graph with order $n$ and treewidth at most $k$,\u00a0then $f_d(G)\\ge\\lceil{(2dn+2)\/(kd+d+1)}\\rceil$,\u00a0unless $G\\in\\{K_{1,1,3},K_{2,3}\\}$ and $k=d=2$.\u00a0We give examples that show that this bound is tight\u00a0to within $1$.We conjecture a bound for $d=1$: $f_1(G) \\ge\\lceil{2n\/(k+2)}\\rceil$,\u00a0which would also be tight to within $1$,\u00a0and we prove it for $k\\le 3$.\u00a0For $k\\ge 4$ the conjecture remains open, and we prove a weaker bound:\u00a0$f_1(G)\\ge (2n+2)\/(2k+3)$.\u00a0We also examine the cases $d=0$ and $k=0,1$.Lastly, we consider open problems relating to $f_d$\u00a0for graphs on a given surface, rather than graphs of bounded treewidth.<\/jats:p>","DOI":"10.37236\/3826","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T01:13:00Z","timestamp":1578705180000},"source":"Crossref","is-referenced-by-count":2,"title":["Maximum Induced Forests in Graphs of Bounded Treewidth"],"prefix":"10.37236","volume":"20","author":[{"given":"Glenn G.","family":"Chappell","sequence":"first","affiliation":[]},{"given":"Michael J.","family":"Pelsmajer","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2013,10,28]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i4p8\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i4p8\/4999","content-type":"application\/zip","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i4p8\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T11:11:46Z","timestamp":1579259506000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v20i4p8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,28]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,10,14]]}},"URL":"https:\/\/doi.org\/10.37236\/3826","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,28]]},"article-number":"P8"}}