论文标题
诱导的子图和树分解V.大顶点的小部分
Induced subgraphs and tree decompositions V. Small components of big vertices
论文作者
论文摘要
Aboulker，Adler，Kim，Sintiari和Trotignon猜想，每个具有界限最大程度和较大树宽的图形都必须作为诱导的子图，一个大的细分壁或大细分壁的线图。这一猜想最近由科霍宁证明，但是在一般情况下（即没有有限的最大程度条件）识别有界树宽障碍的问题仍然很开放。避免“通常的嫌疑人”的大树宽结构的例子是由Sintiari和Trotignon以及Davies建造的。在本说明中，我们的目标是更好地隔离这些示例的特征，从而导致大宽。为此，我们证明了以下结果。令$ g $为图，然后写出$γ（g）$的图表中最大的连接组件的大小，$ g $在一组学位的顶点上至少为3章。这是最好的可能性，从某种意义上说，如果我们在$γ（g）$的定义中替换3个数字，则结论会失败，这是戴维斯的示例所证明的。
Aboulker, Adler, Kim, Sintiari, and Trotignon conjectured that every graph with bounded maximum degree and large treewidth must contain, as an induced subgraph, a large subdivided wall, or the line graph of a large subdivided wall. This conjecture was recently proved by Korhonen, but the problem of identifying the obstacles to bounded treewidth in the general case (that is, without the bounded maximum degree condition) remains wide open. Examples of structures of large treewidth which avoid the "usual suspects" have been constructed by Sintiari and Trotignon, and by Davies. In this note, we aim to better isolate the features of these examples that lead to large treewidth. To this end, we prove the following result. Let $G$ be a graph, and write $γ(G)$ for the size of a largest connected component in the graph induced by $G$ on the set of vertices of degree at least 3. If $γ(G)$ is small and the treewidth of $G$ is large, then $G$ must contain a large subdivided wall or the line graph of a large subdivided wall. This result is the best possible, in the sense that the conclusion fails if we replace 3 by any larger number in the definition of $γ(G)$, as evidenced by Davies' example.
