论文标题
图形类的产品结构，具有有限的树宽
Product structure of graph classes with bounded treewidth
论文作者
论文摘要
我们表明，许多具有有界树宽的图形可以描述为具有较小树宽和有界大小的完整图的图形强产物的子图。为此，定义图类类$ \ MATHCAL {G} $的“基本树宽”，以使其最小非阴性整数$ c $，使得对于某些功能$ f $，对于每个graph $ f $，对于每个graph $ {g \ in \ nathcal {g}} $ $ {h \ boxtimes k_ {f（\ text {tw}（g））}} $的子图的同构。我们介绍了图形的不连接覆盖物，并表明它们确定了任何图形类的基本树宽。使用此结果，我们证明了平面图的类别具有树宽3； $ k_ {s，t} $的类 - 次要的图形具有底层width $ s $（对于$ {t \ geq \ max \ max \ {s，3 \}} $）; $ k_t $ -minor -freagrs的类具有基础树宽$ {t-2} $。通常，我们证明单调类具有且仅当它排除一些固定拓扑小调时，就具有限制了树宽的基础。我们还研究了由排除子图或排除诱导子图定义的图形类的潜在树宽。我们表明，没有$ H $子图的一类图形在且仅当$ h $的每个组件都是细分的恒星时，并且仅当$ h $ h $ h $ h $都是恒星时，只有$ h $的每个组件都是细分的恒星。
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$, for every graph ${G \in \mathcal{G}}$ there is a graph $H$ with ${\text{tw}(H) \leq c}$ such that $G$ is isomorphic to a subgraph of ${H \boxtimes K_{f(\text{tw}(G))}}$. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of $K_{s,t}$-minor-free graphs has underlying treewidth $s$ (for ${t \geq \max\{s,3\}}$); and the class of $K_t$-minor-free graphs has underlying treewidth ${t-2}$. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.
