Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2308.14677 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912127393988608 |
|---|---|
| author | Heinrich, Irene Raßmann, Simon |
| author_facet | Heinrich, Irene Raßmann, Simon |
| contents | The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et. al. 2020), a mass of new results has appeared relating twin width to group theory, model theory, combinatorial optimization, and structural graph theory.
We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph is at most twice its strong tree-width, contrasting nicely with the result of (Bonnet and Déprés 2022), which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain an optimal linear bound on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14677 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Twin-width of graphs with tree-structured decompositions Heinrich, Irene Raßmann, Simon Combinatorics 05C40, 05C05 The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et. al. 2020), a mass of new results has appeared relating twin width to group theory, model theory, combinatorial optimization, and structural graph theory. We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph is at most twice its strong tree-width, contrasting nicely with the result of (Bonnet and Déprés 2022), which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain an optimal linear bound on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph. |
| title | Twin-width of graphs with tree-structured decompositions |
| topic | Combinatorics 05C40, 05C05 |
| url | https://arxiv.org/abs/2308.14677 |