Induced subgraphs of bounded degree and bounded treewidth

Prosenjit Bose, Vida Dujmović, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationGraph-theoretic concepts in computer science
PublisherSpringer
Pages175-186
Number of pages12
Volume3787 LNCS
ISBN (Print)3540310002, 9783540310006
DOIs
Publication statusPublished - 2005
Externally publishedYes
Event31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005 - Metz, France
Duration: 23 Jun 200525 Jun 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3787 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005
CountryFrance
CityMetz
Period23/06/0525/06/05

Cite this

Bose, P., Dujmović, V., & Wood, D. R. (2005). Induced subgraphs of bounded degree and bounded treewidth. In Graph-theoretic concepts in computer science (Vol. 3787 LNCS, pp. 175-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3787 LNCS). Springer. https://doi.org/10.1007/11604686_16