On the Block Number of Graphs

DOI10.1137/17M1145306zbMath1405.05091arXiv1702.04245MaRDI QIDQ4623134

Daniel Weißauer

Publication date: 19 February 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

connectivitytree-decompositionstructure theorem\(k\)-blocks

Mathematics Subject Classification ID

Graph minors (05C83) Connectivity (05C40)

Related Items (5)

Tree-width dichotomy ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs ⋮ Edge degeneracy: algorithmic and structural results ⋮ A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors ⋮ In absence of long chordless cycles, large tree-width becomes a local phenomenon

Cites Work

• Unnamed Item
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Canonical tree-decompositions of a graph that display its \(k\)-blocks
• Connectivity and tree structure in finite graphs
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• A Menger-like property of tree-width: The finite case
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• Highly connected sets and the excluded grid theorem
• Graph searching and a min-max theorem for tree-width
• Quickly excluding a planar graph
• Colouring and Covering Nowhere Dense Graphs
• Graph Theory
• Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)
• Searching for a Visible, Lazy Fugitive
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• A simple linear time algorithm for triangulating three-colored graphs
• $k$-Blocks: A Connectivity Invariant for Graphs
• Polynomial bounds for the grid-minor theorem
• Duality Theorems for Blocks and Tangles in Graphs

This page was built for publication: On the Block Number of Graphs