Induced Subgraphs of Bounded Degree and Bounded Treewidth
| dc.creator | Bose, Prosenjit | |
| dc.creator | Dujmovic, Vida | |
| dc.creator | Wood, David R. | |
| dc.date | 2005-05-19 | |
| dc.date.accessioned | 2026-07-07T06:33:53Z | |
| dc.date.available | 2026-07-07T06:33:53Z | |
| dc.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$. | |
| dc.description | A short version of this paper will appear in the proceedings of WG 2005 (Lecture Notes in Computer Science, Springer) | |
| dc.identifier | https://arxiv.org/abs/math/0505415 | |
| dc.identifier | http://arxiv.org/abs/math/0505415 | |
| dc.identifier | Contributions to Discrete Mathematics, 1(1):88-105, 2006. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/99344 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69 | |
| dc.title | Induced Subgraphs of Bounded Degree and Bounded Treewidth | |
| dc.type | text |