Maximum Induced Forests in Graphs of Bounded Treewidth

Abstract

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\ge 2$ and $n\ge 1$, if $G$ is a graph with order $n$ and treewidth at most $k$, then $f_d(G)\ge\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) \ge\lceil{2n/(k+2)}\rceil$, which would also be tight to within $1$, and we prove it for $k\le 3$. For $k\ge 4$ the conjecture remains open, and we prove a weaker bound: $f_1(G)\ge (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.