论文标题
诱导的子图和树分解VI。带有2个切割的图形
Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
论文作者
论文摘要
本文继续进行一系列论文，调查以下问题：哪些遗传图类具有树宽的界限？我们将其称为图$ t $ - 清洁，如果它不包含作为诱导子图的完整图$ k_t $，完整的两部分图$ k_ {t，t，t} $，$（t \ times t）$ wall和a $（t \ times t）$（t \ times t）$ wall的$（t \ times t）$ wall的细分。众所周知，有界树宽的图必须为$ t $ $ t $ $ t $;但是，每个$ t $ - 清洁图都具有界限的树宽并不是。在本文中，我们表明，三种类型的切割组，即集合切割组，2个切割和1结合，与树宽和彼此之间的相互作用很好地相互作用，因此这些切割方法可分解成基本的有界树宽的基本类别的图形。我们将此结果应用于两个遗传图类别，即（$ isk_4 $，wheel）的类别 - 无独特的和弦，没有周期的图形。以前研究了这些类别，并获得了两个类别的分解定理。我们的主要结果是，$ t $ -CLEAN（$ isk_4 $，wheel）的图形图具有有界的树宽，并且$ t $ clean图形没有循环，具有独特的和弦具有有界的treewidth。
This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph $t$-clean if it does not contain as an induced subgraph the complete graph $K_t$, the complete bipartite graph $K_{t, t}$, subdivisions of a $(t \times t)$-wall, and line graphs of subdivisions of a $(t \times t)$-wall. It is known that graphs with bounded treewidth must be $t$-clean for some $t$; however, it is not true that every $t$-clean graph has bounded treewidth. In this paper, we show that three types of cutsets, namely clique cutsets, 2-cutsets, and 1-joins, interact well with treewidth and with each other, so graphs that are decomposable by these cutsets into basic classes of bounded treewidth have bounded treewidth. We apply this result to two hereditary graph classes, the class of ($ISK_4$, wheel)-free graphs and the class of graphs with no cycle with a unique chord. These classes were previously studied and decomposition theorems were obtained for both classes. Our main results are that $t$-clean ($ISK_4$, wheel)-free graphs have bounded treewidth and that $t$-clean graphs with no cycle with a unique chord have bounded treewidth.
