A Tutte-type canonical decomposition of 3- and 4-connected graphs
Abstract
We provide a unique decomposition of every 4-connected graph into parts that are either quasi-5-connected, cycles of triangle-torsos and 3-connected torsos on \(\leqslant 5\) vertices, generalised double-wheels, or thickened \(K_{4,m}\)'s. The decomposition can be described in terms of a tree-decomposition but with edges allowed in the adhesion-sets. Our construction is explicit, canonical, and exhibits a defining property of the Tutte-decomposition.
Fields of Study & Subjects
Structural Analysis and Optimization
Advanced Graph Theory Research
Digital Image Processing Techniques
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 2942–3021
- Publication date
- 1 January 2026
- Language
- EN