Induced Subgraphs of Bounded Degree and Bounded Treewidth

Bose, Prosenjit; Dujmovic, Vida; Wood, David R.

Induced Subgraphs of Bounded Degree and Bounded Treewidth

Authors

Bose, Prosenjit

Dujmovic, Vida

Wood, David R.

Description

We prove that for all $0\leq t\leq k$ and $d\geq 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$.
A short version of this paper will appear in the proceedings of WG 2005 (Lecture Notes in Computer Science, Springer)