The treewidth of line graphs

DOI10.1016/j.jctb.2018.03.007zbMath1391.05218arXiv1409.6810MaRDI QIDQ723884

David R. Wood, Daniel J. Harvey

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

treewidth; pathwidth; line graphs; vertex congestion

Mathematics Subject Classification ID

05C38: Paths and cycles

05C12: Distance in graphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C76: Graph operations (line graphs, products, etc.)

Related Items

Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, The treewidth of 2-section of hypergraphs, Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree, Unnamed Item, Treewidth of the \(q\)-Kneser graphs, Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs, Bounded-depth Frege complexity of Tseitin formulas for all graphs, Treewidth of the generalized Kneser graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A minimum degree condition forcing complete graph immersion
• A framework for solving VLSI graph layout problems
• Achievable sets, brambles, and sparse treewidth obstructions
• Derivation of algorithms for cutwidth and related graph layout parameters
• On embedding graphs in trees
• Black-white pebbles and graph separation
• The vertex separation number of a graph equals its path-width
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Tree-width, path-width, and cutwidth
• On digraph coloring problems and treewidth duality
• On tree width, bramble size, and expansion
• Parameters Tied to Treewidth
• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• Graph minors. II. Algorithmic aspects of tree-width
• The cutwidth of a graph and the vertex separation number of the line graph
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Treewidth of the Line Graph of a Complete Graph
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree