Polynomial treewidth forces a large grid-like-minor

Abstract

Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an $\ell \times \ell$ grid minor is exponential in $\ell$. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A \emph{grid-like-minor of order} $\ell$ in a graph $G$ is a set of paths in $G$ whose intersection graph is bipartite and contains a $K_{\ell }$-minor. For example, the rows and columns of the $\ell \times \ell$ grid are a grid-like-minor of order $\ell +1$. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least $c{\ell }^4\sqrt{\log \ell }$ has a grid-like-minor of order $\ell$. As an application of this result, we prove that the cartesian product $G\square K_2$ contains a $K_{\ell }$-minor whenever $G$ has treewidth at least $c{\ell }^4\sqrt{\log \ell }$.

v2: The bound in the main result has been improved by using the Lovasz Local Lemma. v3: minor improvements, v4: final section rewritten

References in corpus (1)

• Clique Minors in Cartesian Products of Graphs

Cited by in corpus (8)

• Complexity of Inference in Graphical Models
• Clique Minors in Cartesian Products of Graphs
• A tight Erdős-Pósa function for planar minors
• The Directed Grid Theorem
• Constant congestion brambles in directed graphs
• Parameters Tied to Treewidth
• Lower Bounds for the Complexity of Monadic Second-Order Logic
• A zero-sum problem on graphs