论文标题
具有强额分离器的图形类别的产品结构
Product structure of graph classes with strongly sublinear separators
论文作者
论文摘要
我们研究了遗传图类别的产品结构，该类别承认强烈的均匀分离器。我们表征了诸如恒星强产物的子图和强大大小的完整图。在更确切的结果中，我们表明，如果任何遗传图$ \ nathcal {g} $接纳$ o（n^{1-ε}）$分离器，那么对于任何固定的$δ\ in（0，ε）$ in $ \ n $ vertex graph In $ \ nathcal {g} $ y mathcal {g} $ y Mighth $ y Simes a a y Simes a a y Mighthe y a y Mighth y a y Mighte y a y age a y a $ h y a y a $ h是一个强的产品， $ O（n^{1-ε+δ}）$。如果我们允许$ h $具有树深度$ o（\ log \ log n）$，则此结果为$δ= 0 $。此外，使用经典的等级不等式的网格图形图，我们显示了对$δ$的依赖性，以及上述$ \ text {td}（h）\ in O（\ log \ log \ log \ log n）$绑定的依赖性。我们证明，有界树宽的$ n $ vertex图是带有树深度$ t $的图形的子图和大小$ o（n^{1/t}）$的完整图，这是最好的。最后，我们调查了以下猜想：对于任何属于$ o（n^{1-ε}）$分隔符的任何遗传图类$ \ Mathcal {g} $，每个$ n $ -vertex graph in $ \ Mathcal {g} $都是图形$ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ thebled h $ thece tree tree tree-width and shape y shize $ s $ s $ o（$ o（$ o）的强型子的子分类。我们为各种$ \ MATHCAL {G} $ five的各种类证明了这一点。
We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star and a complete graph of strongly sublinear size. In a more precise result, we show that if any hereditary graph class $\mathcal{G}$ admits $O(n^{1-ε})$ separators, then for any fixed $δ\in(0,ε)$ every $n$-vertex graph in $\mathcal{G}$ is a subgraph of the strong product of a graph $H$ with bounded tree-depth and a complete graph of size $O(n^{1-ε+δ})$. This result holds with $δ=0$ if we allow $H$ to have tree-depth $O(\log\log n)$. Moreover, using extensions of classical isoperimetric inequalties for grids graphs, we show the dependence on $δ$ in our results and the above $\text{td}(H)\in O(\log\log n)$ bound are both best possible. We prove that $n$-vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth $t$ and a complete graph of size $O(n^{1/t})$, which is best possible. Finally, we investigate the conjecture that for any hereditary graph class $\mathcal{G}$ that admits $O(n^{1-ε})$ separators, every $n$-vertex graph in $\mathcal{G}$ is a subgraph of the strong product of a graph $H$ with bounded tree-width and a complete graph of size $O(n^{1-ε})$. We prove this for various classes $\mathcal{G}$ of interest.
