Maximum induced forests in graphs of bounded treewidth

Glenn G. Chappell¹ ; Michael J. Pelsmajer²

¹University of Alaska
²Illinois Institute of Technology

The electronic journal of combinatorics, Tome 20 (2013) no. 4

Résumé

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.

Détail

DOI : 10.37236/3826

Classification : 05C35, 05C05
Mots-clés : treewidth, chordal graph, induced forest