论文标题
图形的边缘分离器不包括未成年人
Edge separators for graphs excluding a minor
论文作者
论文摘要
我们证明，每一个$ n $ vertex $ k_t $ -minor-free Graph $ g $ f $ g $ frg $δ$都有$ f $ o的$ o（t^2（\ log t）^{1/4} \ sqrt {Δn} {δn}）$边缘，使得$ g-f $的每个组件都具有$ g-f $的每个组成部分。这最好是对$ t $的依赖性，并扩展了Diks，Djidjev，Sykora和Vrťo（1993）的早期结果，用于平面图，以及Sykora和Vrťo（1993）的界图。我们的结果是以下更一般结果的结果：$ g $的线图对强型$ h \ boxtimes k _ {\ lfloor p \ rfloor} $的子图是同构的。
We prove that every $n$-vertex $K_t$-minor-free graph $G$ of maximum degree $Δ$ has a set $F$ of $O(t^2(\log t)^{1/4}\sqrt{Δn})$ edges such that every component of $G - F$ has at most $n/2$ vertices. This is best possible up to the dependency on $t$ and extends earlier results of Diks, Djidjev, Sykora, and Vrťo (1993) for planar graphs, and of Sykora and Vrťo (1993) for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of $G$ is isomorphic to a subgraph of the strong product $H \boxtimes K_{\lfloor p \rfloor}$ for some graph $H$ with treewidth at most $t-2$ and $p = \sqrt{(t-3)Δ|E(G)|} + Δ$.
