论文标题
在无孔图的树宽度上
On the tree-width of even-hole-free graphs
论文作者
论文摘要
所有偶数图的类别的类都具有无界的树宽，因为它包含所有完整的图形。最近，构建了一类（均匀，$ k_4 $） - 构建了免费图形，它仍然具有无界的树宽度[Sintiari and Trotignon，2019年]。该类具有无界度，并包含任意大的集团罚款。我们问这是否有必要。 我们证明，对于每个图$ g $，如果$ g $不包括固定的图$ h $作为未成年人，则$ g $具有小树宽，或$ g $包含一个大墙，或者是大墙的线图，如诱导的子图片。这可以看作是罗伯逊（Robertson）和西摩（Seymour）对少量图案的排除网格定理的加强。我们的定理意味着，每个类别的无孔图都不包括固定图作为未成年人都具有有界的树宽。实际上，我们的定理适用于更一般的类：（ theta，prism） - 无图形。这意味着已知的结果，即使平面甚至无孔的图具有有限的树宽度[Da Silva和Linhares销售，离散应用数学2010]。 我们猜想，有界程度的均匀图具有有限的树宽度。如果是真的，这意味着在属性测试的有限度图模型中可以测试甚至可以测试。我们证明了亚地铁图的猜想，并在最多4个（孔，金字塔）的类别（偶数孔，金字塔）的类别的树宽度上给出了一个界限。
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, $K_4$)-free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph $G$, if $G$ excludes a fixed graph $H$ as a minor, then $G$ either has small tree-width, or $G$ contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour's excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graph have bounded tree-width [da Silva and Linhares Sales, Discrete Applied Mathematics 2010]. We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.
