Treewidth of the Line Graph of a Complete Graph |
| |
| Authors: | Daniel J. Harvey David R. Wood |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND STATISTICS, THE UNIVERSITY OF MELBOURNE, PARKVILLE, VICTORIA, AUSTRALIA;2. SCHOOL OF MATHEMATICAL SCIENCES, MONASH UNIVERSITY, CLAYTON, VICTORIA, AUSTRALIA |
| |
| Abstract: | ![]()
In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example—in a certain sense, every graph with large treewidth “contains”  . However, the treewidth of  was not determined exactly. We determine the exact treewidth of the line graph of a complete graph. |
| |
| Keywords: | |
|
|
