Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
复制标题
归纳子图和树分解 I. 有界度的偶孔无图
DOI：
10.1016/j.jctb.2022.05.009
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vušković, Kristina
中科院分区：
文献类型：
--
作者：
Abrishami, Tara;Chudnovsky, Maria;Vušković, Kristina
树宽是一个参数，出现在研究图的小闭类（即在顶点和边删除和边收缩下闭合的类）。它在某种意义上描述了图的全局结构。粗略地说，一个图的树宽为k，如果它可以被一系列大小不超过k的非交叉割集分解成大小不超过k+ 1的块。对遗传图类（即仅在顶点删除下封闭的图类）的研究揭示了一个不同的画面，其中需要大小不一定有界的割集（如星星割集，2-连接及其推广）将图分解为结构化但大小不一定有界的更简单的片段。许多这样的分解定理是已知的复杂的遗传图类，包括偶孔自由图，完美图和其他。这些定理并不像树分解那样描述全局结构，因为它们所保证的割集远非不相交。它们在算法应用中的用途也有限。我们证明了在偶数有界度无洞图的情况下，上一段中描述的割集可以被划分为有界数量的行为良好的集合。这使我们能够证明，甚至洞无图有界度有界树宽，解决了Aboulker等人的猜想。（2021）[1]。因此，它遵循许多算法问题可以在多项式时间内解决这个类，甚至孔自由度是可测试的属性测试的有界度图模型。事实上，我们证明了我们的结果更大的一类图，即类C4-免费奇可签署的有界度的图。
Treewidth is a parameter that emerged from the study of minor closed classes of graphs (ie classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth k if it can be decomposed by a sequence of noncrossing cutsets of size at most k into pieces of size at most k+ 1. The study of hereditary graph classes (ie those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including even-hole-free graphs, perfect graphs and others. These theorems do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by them are far from being noncrossing. They are also of limited use in algorithmic applications. We show that in the case of even-hole-free graphs of bounded degree the cutsets described in the previous paragraph can be partitioned into a bounded number of well-behaved collections. This allows us to prove that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker et al.(2021)[1]. As a consequence, it follows that many algorithmic problems can be solved in polynomial time for this class, and that even-hole-freeness is testable in the bounded degree graph model of property testing. In fact we prove our results for a larger class of graphs, namely the class of C 4-free odd-signable graphs with bounded degree.
登录
查看更多内容
具有星割集和 2-连接的偶孔无图分解
DOI：
10.1016/j.jctb.2012.10.001
发表时间：
2013
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Da Silva M
通讯作者：
Da Silva M
无偶孔图第二部分：识别算法
影响因子：
0.9
作者：
M. Conforti;G. Cornuéjols;Ajai Kapoor;Kristina Vuskovic
通讯作者：
Kristina Vuskovic
归纳子图和树分解 II。
DOI：
10.1016/j.jctb.2023.10.005
发表时间：
2021
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Tara Abrishami;M. Chudnovsky;Cemil Dibek;Sepehr Hajebi;Pawel Rzka.zewski;S. Spirkl;Kristina Vuvskovi'c
通讯作者：
Kristina Vuvskovi'c
无 Kn, n 的团宽有界图的树宽
DOI：
10.1007/3-540-40064-8_19
发表时间：
2000
期刊：
J. Log. Comput.
影响因子：
--
作者：
Frank Gurski;Egon Wanke
通讯作者：
Egon Wanke
DOI：
10.1016/j.jctb.2005.10.006
发表时间：
2006-07
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Sang-il Oum;P. Seymour
通讯作者：
Sang-il Oum;P. Seymour