论文标题
诱导的子图和树分解I.
Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
论文作者
论文摘要
树宽是从研究次要封闭类图的研究中出现的参数（即在顶点和边缘删除下封闭的类，以及边缘收缩）。从某种意义上说，它描述了图的全局结构。粗略地，如果可以用一系列最多$ k $的非交叉切割量（最多$ k+1 $）分解为$ k $的一系列非交叉切割，则具有树宽$ k $。对遗传图类别的研究（即仅在顶点缺失下关闭的类别）揭示了不同的图像，其中不一定限制的切割（例如，恒星切割，2-粘合物及其概括）将图形分解为较简单的碎片，这些碎片结构结构，不一定是尺寸的。许多这样的分解定理以复杂的遗传图类别而闻名，包括无孔的图，完美的图和其他。这些定理在树分解所做的意义上并没有描述全球结构，因为它们保证的剪裁远非没有交叉。它们在算法应用中的用途也有限。 我们表明，在有界程度的无孔图的情况下，上一段中描述的切割组可以分为有限数量的良好数量。这使我们能够证明具有有界程度的无孔图具有有界的树宽，从而解决了Aboulker，Adler，Kim，Sintiari和Trotignon的猜想[Arxiv：2008.05504]。结果，因此可以在该类别的多项式时间内解决许多算法问题，并且在属性测试的界度图模型中可以测试甚至可以测试。实际上，我们证明了较大类图的结果，即$ c_4 $ free-free-free-odsable-signable图形的类别。
Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. 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 (i.e. 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, Adler, Kim, Sintiari and Trotignon [arXiv:2008.05504]. 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.
