### 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 language | English |
---|---|

Title of host publication | Graph-theoretic concepts in computer science |

Publisher | Springer |

Pages | 175-186 |

Number of pages | 12 |

Volume | 3787 LNCS |

ISBN (Print) | 3540310002, 9783540310006 |

DOIs | |

Publication status | Published - 2005 |

Externally published | Yes |

Event | 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005 - Metz, France Duration: 23 Jun 2005 → 25 Jun 2005 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 3787 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005 |
---|---|

Country | France |

City | Metz |

Period | 23/06/05 → 25/06/05 |

## Cite this

*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