Parameters tied to treewidth
From MaRDI portal
Abstract: Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight.
Recommendations
Cites work
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1870231 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- A partial k-arboretum of graphs with bounded treewidth
- Achievable sets, brambles, and sparse treewidth obstructions
- Clique minors in Cartesian products of graphs
- Coloring with no 2-colored \(P_4\)'s
- Complexity of Finding Embeddings in a k-Tree
- Constant-degree graph expansions that preserve treewidth
- Fractional colouring and Hadwiger's conjecture
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Graph searching and a min-max theorem for tree-width
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Highly connected sets and the excluded grid theorem
- Incidence matrices and interval graphs
- Layout of Graphs with Bounded Tree-Width
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Multiplicities of eigenvalues and tree-width of graphs
- Nonrepetitive colorings of graphs of bounded tree-width
- On simple characterizations of k-trees
- On the parameterized intractability of monadic second-order logic
- On tree width, bramble size, and expansion
- Polynomial treewidth forces a large grid-like-minor
- Quickly excluding a planar graph
- S-functions for graphs
- Some recent progress and applications in graph minor theory
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Tree-width and planar minors
- Treewidth lower bounds with brambles
- h-quasi planar drawings of bounded treewidth graphs in linear area
Cited in
(53)- Treewidth of graphs with balanced separations
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- Separating layered treewidth and row treewidth
- Characterizing Tseitin-formulas with short regular resolution refutations
- On the tree-depth and tree-width in heterogeneous random graphs
- Directed path-decompositions
- Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
- On Ramsey Size-Linear Graphs and Related Questions
- The product structure of squaregraphs
- Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree
- Grid minors and products
- Product structure of graph classes with bounded treewidth
- Track layouts, layered path decompositions, and leveled planarity
- Product structure extension of the Alon-Seymour-Thomas theorem
- Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
- Treewidth 2 in the planar graph product structure theorem
- Induced subgraphs and path decompositions
- Orthogonal tree decompositions of graphs
- Clustered 3-colouring graphs of bounded degree
- Structural properties of graph products
- Graph product structure for non-minor-closed classes
- The treewidth of line graphs
- Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
- Tree densities in sparse graph classes
- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Edge-treewidth: algorithmic and combinatorial properties
- Minimum separator reconfiguration
- COP numbers of periodic graphs
- An improved planar graph product structure theorem
- Beating treewidth for average-case subgraph isomorphism
- On the treewidth of toroidal grids
- The treewidth of 2-section of hypergraphs
- Product structure of graph classes with bounded treewidth
- Treewidth, Circle Graphs, and Circular Drawings
- Induced subgraphs and tree decompositions V. one neighbor in a hole
- Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
- Tree-partitions with bounded degree trees
- Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- Fragile minor-monotone parameters under a random edge perturbation
- Product structure of graphs with an excluded minor
- Graph parameters, universal obstructions, and WQO
- The Size Ramsey Number of Graphs with Bounded Treewidth
- Induced subgraphs and tree decompositions. XIV: Non-adjacent neighbours in a hole
- On strict brambles
- Notes on graph product structure theory
- A grid theorem for strong immersions of walls
- On balanced separators, treewidth, and cycle rank
- Better bounds for poset dimension and boxicity
- Graphs of linear growth have bounded treewidth
- Clustered colouring of graph products
- Domino Treewidth
This page was built for publication: Parameters tied to treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978180)
