English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In a reduction sequence of a graph, vertices are successively identifieduntil 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\'e and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ tobe the minimum integer $k$ such that there is a reduction sequence of $G$ inwhich 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.\ forbounded twin-width. In many instances, we also make quantitative improvements.For example, all previous upper bounds on the twin-width of planar graphs wereat 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$\gamma$ are $O(\gamma)$. Lastly, we show that fixed powers of graphs in aproper minor-closed class have bounded reduced bandwidth (irrespective of thedegree of the vertices). In particular, we show that map graphs of Euler genus$\gamma$ have reduced bandwidth $O(\gamma^4)$. Lastly, we separate twin-widthand reduced bandwidth by showing that any infinite class of expanders excludinga fixed complete bipartite subgraph has unbounded reduced bandwidth, whilethere are bounded-degree expanders with twin-width at most 6.

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)