A new proof of the flat wall theorem

DOI10.1016/J.JCTB.2017.09.006MaRDI QIDQ684127zbMATH OpenOpenAlexFDO

Authors Robin Thomas, Paul Wollan, Ken-ichi Kawarabayashi

Publication date 9 February 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.6927

zbMATH Keywords

clique minorgraph minorwallflat wall

Mathematics Subject Classification ID

Graph minors (05C83)

Abstract: 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>0 be integers, and let R=49152t^{24}(40t^2+r). An r-wall is obtained from a (2r x 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 subset A of V(G) of size at most 12288t^{24} and an r-subwall W' of W such that V(W') is disjoint from 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 Xcap Y is a subset of the vertex set of the cycle C' that bounds the outer face of W', V(W') is a subset of Y, every peg of W' belongs to X and the graph G[Y] can almost be drawn in the unit disk with the vertices Xcap 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 Xcap 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.

Recommendations

• Improved bounds for the flat wall theorem
• Optimizing the graph minors weak structure theorem
• Highly connected sets and the excluded grid theorem
• The excluded minor structure theorem with planarly embedded wall
• Excluded grid theorem: improved and simplified

Cites work

• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3026377 (Why is no real title available?)
• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Disjoint paths in graphs
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Graph minors. IX: Disjoint crossed paths
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Improved bounds for the flat wall theorem
• Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
• Optimizing the graph minors weak structure theorem
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(9)

• Contraction bidimensionality of geometric intersection graphs
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Contraction-bidimensionality of geometric intersection graphs
• Improved bounds for the flat wall theorem
• Faster parameterized algorithms for modification problems to minor-closed classes
• A more accurate view of the flat wall theorem
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• Optimizing the graph minors weak structure theorem
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm

This page was built for publication: A new proof of the flat wall theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684127)