The treewidth of line graphs

DOI10.1016/J.JCTB.2018.03.007MaRDI QIDQ723884zbMATH OpenOpenAlexWikidataFDO

Authors Daniel J. Harvey, David R. Wood

Publication date 24 July 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.6810

zbMATH Keywords

treewidthpathwidthline graphsvertex congestion

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

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.

Recommendations

• Analytic approximations of statistical quantities and response of noisy oscillators
• Treewidth of the line graph of a complete graph
• Line graphs of bounded clique-width
• Pathwidth of planar and line graphs
• Computational aspects of treewidth for graph

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1769334 (Why is no real title available?)
• A framework for solving VLSI graph layout problems
• A minimum degree condition forcing complete graph immersion
• Achievable sets, brambles, and sparse treewidth obstructions
• Black-white pebbles and graph separation
• Can you beat treewidth?
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Derivation of algorithms for cutwidth and related graph layout parameters
• Graph minors. II. Algorithmic aspects of tree-width
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• On digraph coloring problems and treewidth duality
• On embedding graphs in trees
• On the Cutwidth and the Topological Bandwidth of a Tree
• On tree width, bramble size, and expansion
• Parameters tied to treewidth
• The cutwidth of a graph and the vertex separation number of the line graph
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• The vertex separation number of a graph equals its path-width
• Topological Bandwidth
• Tree-width, path-width, and cutwidth
• Treewidth of the line graph of a complete graph

Cited in

(16)

• Treewidth of the \(q\)-Kneser graphs
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• scientific article; zbMATH DE number 7731184 (Why is no real title available?)
• scientific article; zbMATH DE number 7559371 (Why is no real title available?)
• Properties of uniformly \(3\)-connected graphs
• scientific article; zbMATH DE number 5811090 (Why is no real title available?)
• Treewidth of the generalized Kneser graphs
• Analytic approximations of statistical quantities and response of noisy oscillators
• The treewidth of 2-section of hypergraphs
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• Parameterised and fine-grained subgraph counting, modulo 2
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Tree-width and circumference of graphs
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• Treewidth of the line graph of a complete graph

This page was built for publication: The treewidth of line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q723884)