We prove that for all integers $kgeq tgeq 0$ and $dgeq 2k$, every graph $G$ with treewidth at most $k$ has a `large' induced subgraph $H$, where $H$ has treewidth at most $t$ and every vertex in $H$ has degree at most $d$ in $G$. The order of $H$ depends on $t$, $k$, $d$, and the order of $G$. With $t=k$, we obtain large sets of bounded degree vertices. With $t=0$, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of $H$ are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size $k$ has a maximum independent set in which every vertex has degree at most $2k$.
展开▼
机译：我们证明，对于所有整数$ kgeq tgeq 0 $和$ dgeq 2k $，每个树宽度最大为$ k $的图$ G $都有一个“大”诱导子图$ H $，其中$ H $的树宽度最多为$ t $和$ H $中的每个顶点在$ G $中的度数最多为$ d $。 $ H $的顺序取决于$ t $，$ k $，$ d $和$ G $的顺序。通过$ t = k $，我们获得了大范围的有界顶点。在$ t = 0 $的情况下，我们获得了大型独立的有界度集。在这两种情况下，我们在$ H $量级上的界限都很严格。对于树中有界度独立集，我们描述了极值图。最后，我们证明了具有最大集团大小$ k $的区间图具有最大独立集，其中每个顶点的度数最多为$ 2k $。
展开▼
