Product structure of graphs excluding a topological minor

Abstract

We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $\mathrm{td}(X)\le h$, there exists a positive integer $c(X,t)$ such that every graph $G$ with $\mathrm{tw}(G)<t$ that excludes $X$ as a topological minor is isomorphic to a subgraph of $H⊠K_{c(X,t)}$ for some graph $H$ with $\mathrm{tw}(H)<2^{h+1}-1$. This extends a result by Ding and Oporowski (Journal of Graph Theory; 1995), which states that for all positive integers $\Delta$ and $t$, here exists a positive integer $f(\Delta ,t)$ such that every graph $G$ with $\mathrm{tw}(G)<t$ and $\Delta (G)\le \Delta$ is isomorphic to a subgraph of $T⊠K_{f(\Delta ,t)}$ for some tree $T$.

arXiv comment18 pages, 3 figures