Treewidth of the Line Graph of Complete and Complete Multipartite Graphs
Daniel J. Harvey, David R. Wood · arXiv (Cornell University) · 2012
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.