Induced subgraphs and tree decompositions V. one neighbor in a hole
Induced subgraphs and tree decompositions V. one neighbor in a hole
复制标题
诱导子图和树分解 V. 洞中的一个邻居
DOI：
10.1002/jgt.23055
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
S. Spirkl
中科院分区：
文献类型：
--
作者：
Tara Abrishami;M. Chudnovsky;Sepehr Hajebi;S. Spirkl
大树宽图不可避免的导出子图是什么？众所周知，答案必须包括完整图、完整二部图、墙的所有细分以及墙的所有细分的线图（我们将这些图称为“基本树宽障碍物”）。因此，很自然地会问，排除基本树宽障碍物作为导出子图的图是否具有有界树宽。辛蒂亚里和特罗蒂尼翁对这个问题的回答是否定的。他们的反例，所谓的“分层轮子”，包含轮子，其中轮子由一个孔（即长度至少为四的诱导循环）以及一个顶点组成，该顶点在该孔中至少有三个邻居。这导致人们问，排除轮子和基本树宽障碍物作为导出子图的图是否具有有界树宽。这也被证明是错误的，因为戴维斯最近的示例图具有大树宽，没有轮子并且没有基本树宽障碍物作为诱导子图。然而，在戴维斯的例子中，存在孔和顶点（孔之外），其中有两个邻居。在这里，我们证明，在具有大树宽且没有基本障碍的图中，具有至少两个邻居的顶点的洞是不可避免的。我们的主要结果是，每个顶点在每个洞（不包含它）中最多有一个邻居并且将基本树宽障碍物排除为诱导子图的图具有有界树宽。
What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called “layered wheels,” contain wheels, where a wheel consists of a hole (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth.
不包含环且节点上至少有两个邻居的图
DOI：
10.48550/arxiv.1309.1841
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Aboulker P
通讯作者：
Aboulker P
归纳子图和树分解 I. 有界度的偶孔无图
DOI：
10.1016/j.jctb.2022.05.009
发表时间：
2022
期刊：
Series B
影响因子：
--
作者：
Abrishami, Tara;Chudnovsky, Maria;Vušković, Kristina
通讯作者：
Vušković, Kristina
归纳子图和树分解 III。
影响因子：
--
作者：
Chudnovsky, Maria;Abrishami, Tara;Hajebi, Sepehr;Spirkl, Sophie
通讯作者：
Spirkl, Sophie