Maximum Induced Forests in Graphs of Bounded Treewidth

[摘要] 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$ an

[学科分类] 离散数学和组合数学

[关键词] Treewidth;chordal graph;induced forest