Treewidth of the line graph of a complete graph

Daniel Harvey, David Wood

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

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 L(Kn). However, the treewidth of L(Kn) was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.
Original languageEnglish
Pages (from-to)48 - 54
Number of pages7
JournalJournal of Graph Theory
Volume79
Issue number1
DOIs
Publication statusPublished - 2015

Cite this