Polynomial treewidth forces a large grid-like-minor - Mathematics > CombinatoricsReport as inadecuate

Polynomial treewidth forces a large grid-like-minor - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Robertson and Seymour proved that every graph with sufficiently largetreewidth contains a large grid minor. However, the best known bound on thetreewidth that forces an $\ell\times\ell$ grid minor is exponential in $\ell$.It is unknown whether polynomial treewidth suffices. We prove a result in thisdirection. A \emph{grid-like-minor of order} $\ell$ in a graph $G$ is a set ofpaths 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 polynomialtreewidth forces a large grid-like-minor. In particular, every graph withtreewidth 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}$.

Author: Bruce A. Reed, David R. Wood

Source: https://arxiv.org/

Related documents