Graph minors and minimum degree

zbMATH Open1204.05089arXiv0812.1064MaRDI QIDQ612934FDOQ612934

Authors: Gašper Fijavž, David R. Wood 

Publication date: 16 December 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $widehat{mathcalD}_k$. This paper discusses $widehat{mathcalD}_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 $widehat{mathcalD}_k$, and this bound is best possible. We characterise the graphs in $widehat{mathcalD}_{k+1}$ that can be obtained from a graph in $widehat{mathcalD}_k$ by adding one new vertex. For $kleq3$ every graph in $widehat{mathcalD}_k$ is $(k+1)$-connected, but for large $k$, we exhibit graphs in $widehat{mathcalD}_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{mathcalD}_k$, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.

Full work available at URL: https://arxiv.org/abs/0812.1064

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Minimum degree and graph minors
• scientific article; zbMATH DE number 4144031
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Small minors in dense graphs
• A lower bound on the average degree forcing a minor

zbMATH Keywords

minimum degreegraph minorRobertson-Seymour graph minor theorem

Mathematics Subject Classification ID

Graph minors (05C83)

Cited In (7)

• Minimum degree condition for a graph to be knitted
• Minimum degree and graph minors
• Title not available (Why is that?)
• Graph minors. XII: Distance on a surface
• Minimum gradation in greyscales of graphs
• Title not available (Why is that?)
• Graph minor theory

This page was built for publication: Graph minors and minimum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612934)