Graph Minors and Minimum Degree

Original · EN

Let Dₖ be the class of graphs for which every minor has minimum degree at most k. Then Dₖ is closed under taking minors. By the Robertson-Seymour graph minor theorem, Dₖ is characterised by a finite family of minor-minimal forbidden graphs, which we denote by Dₖ. This paper discusses Dₖ 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 Dₖ, and this bound is best possible. We characterise the graphs in Dₖ₊₁ that can be obtained from a graph in Dₖ by adding one new vertex. For k≤ 3 every graph in Dₖ is (k+1)-connected, but for large k, we exhibit graphs in Dₖ with connectivity 1. In fact, we construct graphs in Dₖ with arbitrary block structure. We characterise the complete multipartite graphs in Dₖ, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.