Loading...
Please wait, while we are loading the content...
Similar Documents
Induced subgraphs of bounded degree and bounded treewidth (2008).
| Content Provider | CiteSeerX |
|---|---|
| Author | Bose, Prosenjit Dujmović, Vida Wood, David R. |
| Abstract | We prove that for all 0 ≤ t ≤ k and d ≥ 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. |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Bounded Treewidth Maximum Clique Size Degree Vertex Large Independent Set Maximum Independent Set Interval Graph Large Set Large Induced Subgraph Bounded Degree Independent Set Extremal Graph Bounded Degree |
| Content Type | Text |
