Maximum Induced Forests in Graphs of Bounded Treewidth

Electronic Journal Of Combinatorics

Glenn G. Chappell¹ 

关键词: Treewidth;    chordal graph;    induced forest;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

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

【 授权许可】

Others