Daniel J. Harvey, David R. Wood
Published 2012-10-31, updated 2014-08-01Version 2
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.
Comments: 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
The Riemann-Roch theorem for graphs and the rank in complete graphs
Nim on the Complete Graph
Spectral characterizations of almost complete graphs
![QR code for arXiv:1210.8205 [math.CO]](http://oss.arxitics.com/images/favicon.svg)