The treewidth of line graphs

Daniel J. Harvey, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

Abstract

The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph G is equivalent to determining the minimum vertex congestion of an embedding of G into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of G. These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth.

Original languageEnglish
Pages (from-to)157-179
Number of pages23
JournalJournal of Combinatorial Theory, Series B
Volume132
DOIs
Publication statusPublished - 1 Sept 2018

Keywords

  • Line graphs
  • Pathwidth
  • Treewidth
  • Vertex congestion

Cite this