scientific article; zbMATH DE number 1057879
From MaRDI portal
Publication:4352948
\textit{N. Robertson} and \textit{P. D. Seymour} [J. Algorithms 7, 309-322 (1986; Zbl 0611.05017), or J. Comb. Theory, Ser. B 48, No. 2, 227-254 (1990; Zbl 0719.05032)] developed the theory of tree decomposition of graphs and introduced the tree width, a connectivity invariant of graphs (mostly of infinite type) focussing on global properties of graphs. The author discusses a new connectivity invariant, the bramble number, of a graph \(G\). A bramble is a set of connected subgraphs of \(G\), any two of which intersect or are joined by an edge. Then the order of a bramble \(\beta\) is the minimum cardinality of a set of vertices which intersects every element of \(\beta\). The bramble number \(\text{BN} (G)\) of \(G\) is the maximum of the orders of its brambles. For any graph \(G\), the tree width of \(G\) is equal to \(\text{BN} (G)-1\), see also \textit{P. D. Seymour} and \textit{R. Thomas} [J. Comb. Theory, Ser. B 58, No. 1, 22-23 (1993; Zbl 0795.05110)]. Besides the proof of this theorem, the author examines also the structure of graphs with large bramble numbers and resolves many questions on such graphs. For the entire collection see [Zbl 0869.00029].
Recommendations
- On the connectivity index of trees
- Trees of extremal connectivity index
- Connected tree-width
- Bounding connected tree-width
- On connectivities of tree graphs
- Tree-Related Widths of Graphs and Hypergraphs
- Tree-width and circumference of graphs
- New characterisations of tree-based networks and proximity measures
- scientific article; zbMATH DE number 772777
- Treewidth: Characterizations, Applications, and Computations
Cited in
(97)- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Linear connectivity forces large complete bipartite minors
- Brambles and independent packings in chordal graphs
- Submodular partition functions
- Graph minors. X: Obstructions to tree-decomposition
- Edge-disjoint odd cycles in graphs with small chromatic numbers
- Highly connected sets and the excluded grid theorem
- Channel assignment on graphs of bounded treewidth
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Computing the branchwidth of interval graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- Directed tree-width
- On matroids of branch-width three.
- Guarded fixed point logics and the monadic theory of countable trees.
- Fork-decompositions of matroids
- Notes on graph product structure theory
- Tree-width dichotomy
- Tangle-tree duality in abstract separation systems
- Half-integral packing of odd cycles through prescribed vertices
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Tangle and ultrafilter: game theoretical interpretation
- Tree-width and the Sherali-Adams operator
- Recent techniques and results on the Erdős-Pósa property
- Layered separators in minor-closed graph classes with applications
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- Hypertree width and related hypergraph invariants
- Approximating clique-width and branch-width
- On tree width, bramble size, and expansion
- Canonical tree-decompositions of finite graphs. II. Essential parts
- Induced disjoint paths in circular-arc graphs in linear time
- The relative clique-width of a graph
- On strict brambles
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Edge-disjoint odd cycles in 4-edge-connected graphs
- Tangle and Maximal Ideal
- Planar k-path in subexponential time and polynomial space
- Digraphs of bounded width
- Coloring immersion-free graphs
- Erdös-Pósa Property of Obstructions to Interval Graphs
- Brambles, prisms and grids
- Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs
- Pathwidth of outerplanar graphs
- Towards the graph minor theorems for directed graphs
- An Improved Algorithm for Finding Cycles Through Elements
- Maximum induced forests in graphs of bounded treewidth
- Connectivity and tree structure in finite graphs
- Grid minors in damaged grids
- The disjoint paths problem in quadratic time
- Nordhaus-Gaddum for treewidth
- Linkless and flat embeddings in 3-space
- Packing cycles through prescribed vertices under modularity constraints
- Branch decompositions and minor containment
- Sparse graphs of high gonality
- Orthogonal tree decompositions of graphs
- The degree-diameter problem for sparse graph classes
- Finding disjoint paths in split graphs
- Packing and covering induced subdivisions
- Tree densities in sparse graph classes
- An improvement of Reed's treewidth approximation
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Better bounds for poset dimension and boxicity
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
- Structure of graphs with locally restricted crossings
- Treewidth computations. II. Lower bounds
- Bounding connected tree-width
- List-coloring graphs without subdivisions and without immersions
- Clustered 3-colouring graphs of bounded degree
- Computing with tangles
- Constant Congestion Brambles
- Tangle bases: Revisited
- Erdős–Pósa property of obstructions to interval graphs
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- The product structure of squaregraphs
- Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Polynomial treewidth forces a large grid-like-minor
- The splitting power of branching programs of bounded repetition and CNFs of bounded width
- \(K_{6}\) minors in large 6-connected graphs
- Linear bounds on treewidth in terms of excluded planar minors
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Characterising 4-tangles through a connectivity property
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Treewidth 2 in the planar graph product structure theorem
- Structural properties of graph products
- Boolean-width of graphs
- Connected tree-width
- Shallow brambles
- Clustered coloring of graphs excluding a subgraph and a minor
- Lower bounds for treewidth of product graphs
- Some recent progress and applications in graph minor theory
- Treewidth lower bounds with brambles
- Treewidth computations. I: Upper bounds
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- Recent developments on graphs of bounded clique-width
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4352948)
