Maximum induced forests in graphs of bounded treewidth (Q396918): Difference between revisions

Summary: Given a nonnegative integer \(d\) and a graph \(G\), let \(f_d(G)\) be the maximum order of an induced forest in \(G\) having maximum degree at most \(d\). We seek lower bounds for \(f_d(G)\) based on the order and treewidth of \(G\). We show that, for all \(k,d\geq 2\) and \(n\geq 1\), if \(G\) is a graph with order \(n\) and treewidth at most \(k\), then \(f_d(G)\geq\lceil{(2dn+2)/(kd+d+1)}\rceil\), unless \(G\in\{K_{1,1,3},K_{2,3}\}\) and \(k=d=2\). We give examples that show that this bound is tight to within 1. We conjecture a bound for \(d=1: f_1(G) \geq\lceil{2n/(k+2)}\rceil\), which would also be tight to within 1, and we prove it for \(k\leq 3\). For \(k\geq 4\) the conjecture remains open, and we prove a weaker bound: \(f_1(G)\geq (2n+2)/(2k+3)\). We also examine the cases \(d=0\) and \(k=0,1\). Lastly, we consider open problems relating to \(f_d\) for graphs on a given surface, rather than graphs of bounded treewidth.