Quasi-4-Connected Components
From MaRDI portal
Abstract: We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3 that remove a single vertex. Moreover, we give a cubic time algorithm computing the decomposition of a given graph. Our decomposition into quasi-4-connected components refines the well-known decompositions of graphs into biconnected and triconnected components. We relate our decomposition to Robertson and Seymour's theory of tangles by establishing a correspondence between the quasi-4-connected components of a graph and its tangles of order 4.
Recommendations
- The structure of quasi 4-connected graphs
- Connected quandles of size \(pq\) and \(4p\)
- Quintessential quartic quasi-topological quartet
- scientific article; zbMATH DE number 1051274
- On connected component decompositions of quandles
- Quasiconformal 4-manifolds
- Minors of quasi 4-connected graphs
- 4-connected triangulations and 4-orderedness
- Simply connected quasiregularly elliptic 4-manifolds
- Connected sums of 4-manifolds
Cited in
(11)- Quintessential quartic quasi-topological quartet
- The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem (extended abstract)
- The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
- Quasi 4--8 subdivision
- Every cubic cage is quasi 4-connected
- Local 2-separators
- Connect four and graph decomposition
- Minors of quasi 4-connected graphs
- Characterising 4-tangles through a connectivity property
- Twin-width of graphs with tree-structured decompositions
- Twin-width of graphs with tree-structured decompositions
This page was built for publication: Quasi-4-Connected Components
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598140)
