{
  "id": "1409.6810",
  "version": "v1",
  "published": "2014-09-24T03:39:15.000Z",
  "updated": "2014-09-24T03:39:15.000Z",
  "title": "The Treewidth of Line Graphs",
  "authors": [
    "Daniel J. Harvey",
    "David R. Wood"
  ],
  "comment": "18 pages (including appendices)",
  "categories": [
    "math.CO"
  ],
  "abstract": "The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph $G$ is equivalent to determining the minimum vertex congestion of an embedding of $G$ into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of $G$. These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-24T03:39:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C76"
    ],
    "keywords": [
      "line graph",
      "minimum vertex congestion",
      "sharp lower bounds",
      "algorithmic graph theory",
      "paper studies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.6810H"
    }
  }
}