Graph minors and minimum degree

MaRDI QIDQ612934zbMATHFDO

Authors Gašper Fijavž, David R. Wood

Publication date 16 December 2010

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

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

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

zbMATH Keywords

minimum degreegraph minorRobertson-Seymour graph minor theorem

Mathematics Subject Classification ID

Graph minors (05C83)

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.

Recommendations

• Minimum degree and graph minors
• Publication:3475304
• \(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

Cited in

(7)

• Minimum degree and graph minors
• Graph minor theory
• Minimum gradation in greyscales of graphs
• Minimum degree condition for a graph to be knitted
• Graph minors. XII: Distance on a surface
• scientific article; zbMATH DE number 5525873 (Why is no real title available?)
• scientific article; zbMATH DE number 4144031 (Why is no real title available?)

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)