Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2202.11858 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912669168041984 |
|---|---|
| author | Bonnet, Édouard Kwon, O-joung Wood, David R. |
| author_facet | Bonnet, Édouard Kwon, O-joung Wood, David R. |
| contents | In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al.\ for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced bandwidth at most $466$ and twin-width at most $583$. Our bounds for graphs of Euler genus $γ$ are $O(γ)$. Lastly, we show that fixed powers of graphs in a proper minor-closed class have bounded reduced bandwidth (irrespective of the degree of the vertices). In particular, we show that map graphs of Euler genus $γ$ have reduced bandwidth $O(γ^4)$. Lastly, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_11858 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) Bonnet, Édouard Kwon, O-joung Wood, David R. Combinatorics Discrete Mathematics In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al.\ for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced bandwidth at most $466$ and twin-width at most $583$. Our bounds for graphs of Euler genus $γ$ are $O(γ)$. Lastly, we show that fixed powers of graphs in a proper minor-closed class have bounded reduced bandwidth (irrespective of the degree of the vertices). In particular, we show that map graphs of Euler genus $γ$ have reduced bandwidth $O(γ^4)$. Lastly, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6. |
| title | Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2202.11858 |