A Tutte-type canonical decomposition of 3- and 4-connected graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917265206673408 |
|---|---|
| author | Kurkofka, Jan Planken, Tim |
| author_facet | Kurkofka, Jan Planken, Tim |
| contents | 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 $\leq 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.
As a corollary, we obtain a new Tutte-type canonical decomposition of 3-connected graphs into parts that are either quasi-4-connected, generalised wheels or thickened $K_{3,m}$'s. This decomposition is similar yet different from the tri-separation decomposition.
As an application of the decomposition for 4-connectivity, in a follow-up paper we obtain a new theorem characterising all vertex-transitive finite connected graphs as essentially quasi-5-connected or on a short explicit list of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00760 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Tutte-type canonical decomposition of 3- and 4-connected graphs Kurkofka, Jan Planken, Tim Combinatorics Discrete Mathematics 05C40 (Primary) 05C75, 05C83, 05E18 (Secondary) 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 $\leq 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. As a corollary, we obtain a new Tutte-type canonical decomposition of 3-connected graphs into parts that are either quasi-4-connected, generalised wheels or thickened $K_{3,m}$'s. This decomposition is similar yet different from the tri-separation decomposition. As an application of the decomposition for 4-connectivity, in a follow-up paper we obtain a new theorem characterising all vertex-transitive finite connected graphs as essentially quasi-5-connected or on a short explicit list of graphs. |
| title | A Tutte-type canonical decomposition of 3- and 4-connected graphs |
| topic | Combinatorics Discrete Mathematics 05C40 (Primary) 05C75, 05C83, 05E18 (Secondary) |
| url | https://arxiv.org/abs/2504.00760 |