Premium
Treewidth of the Line Graph of a Complete Graph
Author(s) -
Harvey Daniel J.,
Wood David R.
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21813
Subject(s) - treewidth , mathematics , combinatorics , partial k tree , line graph , discrete mathematics , tree depth , graph minor , graph , outerplanar graph , 1 planar graph , tree decomposition , pathwidth , voltage graph
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 ( K n ) . However, the treewidth of L ( K n ) was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.