Twin-width of subdivisions of multigraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908488438906880 |
|---|---|
| author | Ahn, Jungho Chakraborti, Debsoumya Hendrey, Kevin Oum, Sang-il |
| author_facet | Ahn, Jungho Chakraborti, Debsoumya Hendrey, Kevin Oum, Sang-il |
| contents | For each $d\leq3$, we construct a finite set $F_d$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at least two times, $H$ has twin-width at most $d$ if and only if $G$ has no minor in $F_d$. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs $G$ such that each long subdivision of $G$ has twin-width $4$. As a corollary, we show that the $7\times7$ grid has twin-width $4$, which answers a question of Schidler and Szeider. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_05334 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Twin-width of subdivisions of multigraphs Ahn, Jungho Chakraborti, Debsoumya Hendrey, Kevin Oum, Sang-il Combinatorics Discrete Mathematics 05C35, 05C75 For each $d\leq3$, we construct a finite set $F_d$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at least two times, $H$ has twin-width at most $d$ if and only if $G$ has no minor in $F_d$. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs $G$ such that each long subdivision of $G$ has twin-width $4$. As a corollary, we show that the $7\times7$ grid has twin-width $4$, which answers a question of Schidler and Szeider. |
| title | Twin-width of subdivisions of multigraphs |
| topic | Combinatorics Discrete Mathematics 05C35, 05C75 |
| url | https://arxiv.org/abs/2306.05334 |