论文标题
Alon-Seymour- thomas定理的产品结构扩展
Product structure extension of the Alon--Seymour--Thomas theorem
论文作者
论文摘要
Alon，Seymour和Thomas [1990]证明，每个$ n $ vertex Graph不包括$ k_t $作为未成年人的树宽小于$ t^{3/2} \ sqrt {n} $。 Illingworth，Scott和Wood [2022]最近通过证明每个图形都是带有TreeWidth $ t-2 $的图形的子图，从而完善了这一结果，其中每个顶点都通过完整的订单$ O（\ sqrt {tn}）$炸毁。解决了Illingworth，Scott和Wood [2022]的开放问题，我们证明，树宽的绑定可以减少到$ 4 $，同时保留订单$ o_t（\ sqrt {n}）$。作为Lipton-Tarjan定理的扩展，对于平面图，我们表明可以将树宽进一步减少到$ 2 $，这是最好的。我们将此结果概括为$ k_ {3，t} $ - 少量图形，并带有订单$ o（t \ sqrt {n}）$的爆炸。此设置包括可在任何固定表面上嵌入的图形。
Alon, Seymour and Thomas [1990] proved that every $n$-vertex graph excluding $K_t$ as a minor has treewidth less than $t^{3/2}\sqrt{n}$. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth $t-2$, where each vertex is blown up by a complete graph of order $O(\sqrt{tn})$. Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to $4$ while keeping blowups of order $O_t(\sqrt{n})$. As an extension of the Lipton--Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to $2$, which is best possible. We generalise this result for $K_{3,t}$-minor-free graphs, with blowups of order $O(t\sqrt{n})$. This setting includes graphs embeddable on any fixed surface.
