Graph minors and minimum degree (Q612934)

Summary: 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 \(\widehat{\mathcal D}_k\). This paper discusses \(\widehat{\mathcal D}_k\) and related topics. We obtain four main results: {\parindent=5mm \begin{itemize}\item[1.] We prove that every \((k+1)A\)-regular graph with less than \(\frac43(k+2)\) vertices is in \(\widehat{\mathcal D}_k\), and this bound is best possible. \item[2.] We characterise the graphs in \(\widehat{\mathcal D}_{k+1}\) that can be obtained from a graph in \(\widehat{\mathcal D}_k\) by adding one new vertex. \item[3.] For \(k\leq 3\) every graph in \(\widehat{\mathcal D}_k\) is \((k+1)\)-connected, but for large \(k\), we exhibit graphs in \(\widehat{\mathcal D}_k\) with connectivity 1. In fact, we construct graphs in \({\mathcal D}_k\) with arbitrary block structure. \item[4.] We characterise the complete multipartite graphs in \(\widehat{\mathcal D}_k\), and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth. \end{itemize}}