Graph Minors and Minimum Degree

Abstract

Let ${\mathcal{D}}_k$ be the class of graphs for which every minor has minimum degree at most $k$. Then ${\mathcal{D}}_k$ is closed under taking minors. By the Robertson-Seymour graph minor theorem, ${\mathcal{D}}_k$ is characterised by a finite family of minor-minimal forbidden graphs, which we denote by ${\hat{\mathcal{D}}}_k$. This paper discusses ${\hat{\mathcal{D}}}_k$ and related topics. We obtain four main results: We prove that every $(k+1)$-regular graph with less than $4/3(k+2)$ vertices is in ${\hat{\mathcal{D}}}_k$, and this bound is best possible. We characterise the graphs in ${\hat{\mathcal{D}}}_{k+1}$ that can be obtained from a graph in ${\hat{\mathcal{D}}}_k$ by adding one new vertex. For $k\le 3$ every graph in ${\hat{\mathcal{D}}}_k$ is $(k+1)$-connected, but for large $k$, we exhibit graphs in ${\hat{\mathcal{D}}}_k$ with connectivity 1. In fact, we construct graphs in ${\mathcal{D}}_k$ with arbitrary block structure. We characterise the complete multipartite graphs in ${\hat{\mathcal{D}}}_k$, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.