Canonical graph decompositions via local separations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914408972681216 |
|---|---|
| author | Jacobs, Raphael W. Knappe, Paul Kurkofka, Jan |
| author_facet | Jacobs, Raphael W. Knappe, Paul Kurkofka, Jan |
| contents | Every finite graph $G$ can be decomposed in a canonical way that displays its local connectivity-structure [DJKK26]. These decompositions are defined via a suitable more tree-like covering of $G$, whose tangle-tree structure is projected down to $G$.
The covering graphs needed here are almost always infinite, and their tangle-tree structure is defined in terms of their (global) low-order separations. The canonical decompositions they induce on $G$ are therefore not computable following their definition.
We reconstruct these decompositions of $G$ from finite information in $G$ itself that is sufficiently local to be reflected in the cover. This involves the reconstruction of canonical tangle structure in terms of a new theory of local separations in finite graphs, which we develop for this purpose.
As an application, we find that the canonical graph-decompositions from [DJKK26] are computable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16170 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Canonical graph decompositions via local separations Jacobs, Raphael W. Knappe, Paul Kurkofka, Jan Combinatorics 05C83, 68R10, 57M15, 05C25, 05C40, 05C63, 05C38 Every finite graph $G$ can be decomposed in a canonical way that displays its local connectivity-structure [DJKK26]. These decompositions are defined via a suitable more tree-like covering of $G$, whose tangle-tree structure is projected down to $G$. The covering graphs needed here are almost always infinite, and their tangle-tree structure is defined in terms of their (global) low-order separations. The canonical decompositions they induce on $G$ are therefore not computable following their definition. We reconstruct these decompositions of $G$ from finite information in $G$ itself that is sufficiently local to be reflected in the cover. This involves the reconstruction of canonical tangle structure in terms of a new theory of local separations in finite graphs, which we develop for this purpose. As an application, we find that the canonical graph-decompositions from [DJKK26] are computable. |
| title | Canonical graph decompositions via local separations |
| topic | Combinatorics 05C83, 68R10, 57M15, 05C25, 05C40, 05C63, 05C38 |
| url | https://arxiv.org/abs/2501.16170 |