{
  "id": "1210.8205",
  "version": "v2",
  "published": "2012-10-31T00:49:20.000Z",
  "updated": "2014-08-01T04:09:12.000Z",
  "title": "Treewidth of the Line Graph of Complete and Complete Multipartite Graphs",
  "authors": [
    "Daniel J. Harvey",
    "David R. Wood"
  ],
  "comment": "25 pages, 0 figures. Changes in this revision: One minor error fixed, substantial clean-up of text, title changed. A subset of this paper containing the first Theorem and its proof has been published in the Journal of Graph Theory: Harvey, D. J. and Wood, D. R. (2014), Treewidth of the Line Graph of a Complete Graph. J. Graph Theory. doi: 10.1002/jgt.21813",
  "categories": [
    "math.CO"
  ],
  "abstract": "In recent papers by Grohe and Marx, the treewidth of the line graph of the complete graph is a critical example. We determine the exact treewidth of the line graph of the complete graph. By extending these techniques, we determine the exact treewidth of the line graph of a regular complete multipartite graph. For an arbitrary complete multipartite graph, we determine the treewidth of the line graph up to a lower order term.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-08-01T04:09:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C76"
    ],
    "keywords": [
      "line graph",
      "exact treewidth",
      "regular complete multipartite graph",
      "complete graph",
      "arbitrary complete multipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.8205H"
    }
  }
}