论文标题
降低带宽：在次要类别（及以后）中的两倍宽度的定性增强
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
论文作者
论文摘要
在图的还原序列中，将顶点依次识别，直到图具有一个顶点为止。在每个步骤中，当识别$ u $和$ v $时，每个边缘事件恰好是$ u $和$ v $的一个颜色为红色。 Bonnet，Kim，Thomassé和Watrigant [J. ACM 2022]将图$ g $的双宽度定义为最小整数$ k $，使得$ g $的减少序列最大$ k $。对于任何图表参数$ f $，我们将图$ g $的减少$ f $定义为最小整数$ k $，以使$ g $的减少序列最多具有$ f $ $ f $。我们的重点是具有限制的降低带宽的图形类别，这意味着并且比有限的双宽度（最大程度降低）更强。我们表明，每个适当的次要封闭类都具有降低的带宽限制，这比Bonnet等人的类似结果在质量上要强。在许多情况下，我们还进行了定量改进。例如，平面图的双宽度上的所有上限至少为$ 2^{1000} $。我们表明，平面图最多减少了带宽，最多$ 466 $，最多$ 583 $。我们对Euler属$γ$图表的界限是$ O（γ）$。最后，我们表明，适当的小关闭类中的固定图具有降低带宽（无论顶点程度如何）。特别是，我们表明Euler属$γ$的地图图减少了带宽$ O（γ^4）$。最后，我们通过表明任何无限类别的扩展器（不包括固定完整的两分子段）具有无限型带宽，而最多有界限的扩张器，最多可以将双宽度扩展器具有限制性扩展器，最多可将两分的缩小器分离出双宽度和减少带宽。
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.
