A new proof of the flat wall theorem
A new proof of the flat wall theorem
复制标题
平壁定理的新证明
DOI：
10.1016/j.jctb.2017.09.006
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Wollan, Paul
中科院分区：
文献类型：
--
作者：
Kawarabayashi, Ken-ichi;Thomas, Robin;Wollan, Paul
我们给出了Robertson和Seymour的排除团次要定理的一个较弱形式的初等的、完备的证明和数值改进，如下。设t，r≥1为整数，且R=49152 t24(40 t2+r)。在2r×r-网格中，首先删除每奇数行的奇数条竖边和每一偶数行的每条偶数条竖边，然后删除得到的两个1次顶点，最后对边进行任意细分，得到一个r-墙。在细分之前存在的二次顶点称为R-墙的钉子。设G是一个没有K t子图，W是G中的R-壁，我们证明了存在一个不超过12288 t24的集合A⊆V(G)和W的一个r-子壁W‘使得V(W’)∩A=∅且W‘在下述意义下是G−A中的平坦壁.存在G−A的一个分离(X，Y)，使得X∩Y是圈C‘的一个子集，它限定了W’的外表面，V(W‘)⊆Y，W’的每一个标号都属于X，图G[Y]几乎可以画在单位圆盘上，其中的顶点X∩Y按C‘所确定的顺序画在圆盘的边界上.这里几乎意味着，在重复删除与X∩Y相隔最多三个割集Z的部分图，并添加两端在Z中的所有边之后，断言成立。我们的证明给出了一个算法，即使当r和t是输入实例的一部分时，该算法也以多项式时间运行。从这个意义上讲，证明是自给自足的，因为它只使用在教科书中可以找到证明的结果。
We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t, r≥ 1 be integers, and let R= 49152 t 24 (40 t 2+ r). An r-wall is obtained from a 2 r× r-grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two that existed before the subdivision are called the pegs of the r-wall. Let G be a graph with no K t minor, and let W be an R-wall in G. We prove that there exist a set A⊆ V (G) of size at most 12288 t 24 and an r-subwall W′ of W such that V (W′)∩ A=∅ and W′ is a flat wall in G− A in the following sense. There exists a separation (X, Y) of G− A such that X∩ Y is a subset of the vertex set of the cycle C′ that bounds the outer face of W′, V (W′)⊆ Y, every peg of W′ belongs to X and the graph G [Y] can almost be drawn in the unit disk with the vertices X∩ Y drawn on the boundary of the disk in the order determined by C′. Here almost means that the assertion holds after repeatedly removing parts of the graph separated from X∩ Y by a cutset Z of size at most three, and adding all edges with both ends in Z. Our proof gives rise to an algorithm that runs in polynomial time even when r and t are part of the input instance. The proof is self-contained in the sense that it uses only results whose proofs can be found in textbooks.
登录
查看更多内容
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
DOI：
10.1137/1.9781611973730.20
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Julia Chuzhoy
通讯作者：
Julia Chuzhoy
无 H 小子图的树宽与其最大网格小子之间的线性最小-最大关系
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
M.-H. Hsieh;F. Le Gall;Yusuke Kobayashi
通讯作者：
Yusuke Kobayashi
DOI：
--
发表时间：
1990
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour