Induced Subgraphs of Bounded Degree and Bounded Treewidth

Prosenjit Bose, Vida Dujmovic, David R. Wood

We prove that for all $0\le t\le k$ and $d\ge 2k$, every graph $G$ with treewidth at most $k$ has a `large' induced subgraph $H$, where $H$ has treewidth at most $t$ and every v…