{
  "id": "math/0505415",
  "version": "v1",
  "published": "2005-05-19T13:39:36.000Z",
  "updated": "2005-05-19T13:39:36.000Z",
  "title": "Induced Subgraphs of Bounded Degree and Bounded Treewidth",
  "authors": [
    "Prosenjit Bose",
    "Vida Dujmovic",
    "David R. Wood"
  ],
  "comment": "A short version of this paper will appear in the proceedings of WG 2005 (Lecture Notes in Computer Science, Springer)",
  "journal": "Contributions to Discrete Mathematics, 1(1):88-105, 2006.",
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-05-19T13:39:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "induced subgraph",
      "bounded treewidth",
      "maximum independent set",
      "bounded degree independent sets",
      "large independent sets"
    ],
    "tags": [
      "journal article",
      "lecture notes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......5415B"
    }
  }
}