
arXiv: 0812.1064
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: We prove that every $(k+1)$-regular graph with less than $\frac{4}{3}(k+2)$ vertices is in $\widehat{\mathcal{D}}_k$, and this bound is best possible. 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. 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. We characterise the complete multipartite graphs in $\widehat{\mathcal{D}}_k$, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.
05C83, 05C40, FOS: Mathematics, Mathematics - Combinatorics, Graph minors, Combinatorics (math.CO), Robertson-Seymour graph minor theorem, graph minor, minimum degree
05C83, 05C40, FOS: Mathematics, Mathematics - Combinatorics, Graph minors, Combinatorics (math.CO), Robertson-Seymour graph minor theorem, graph minor, minimum degree
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
