Planar graphs with no 6-wheel minor
type: Item
instance of: scholarly article
title: Planar graphs with no 6-wheel minor
zbMATH Open document ID: 0792.05115
DOI: 10.1016/0012-365X(93)90565-B
author: Bradley S. Gubser
published in: Discrete Mathematics
publication date: 1994-07-24T00:00:00Z
review text: By Tutte's wheels theorem [Nederl. Akad. Wet., Proc. Ser. A 64, 441-455 (1961; Zbl 0101.409)], every simple 3-connected graph can be built from some wheel graph by adding edges and splitting vertices. Moreover, \textit{B. Oporowski}, \textit{J. Oxley} and \textit{R. Thomas} [J. Comb. Theory, Ser. B 57, 239-257 (1993; Zbl 0728.05041)] showed that, for all \(n\geq 3\), there are only finitely many simple 3-connected planar graphs having no minor isomorphic to the \(n\)-spoked wheel \(W_ n\). However, the last paper made no attempt to give a practical bound on the size of a largest simple 3-connected planar graph with no \(W_ n\)-minor. In the present paper, the author lists thirty-eight graphs, each with sixteen or seventeen edges, and shows that every simple 3-connected planar graph with no \(W_ 6\)-minor is a minor of one of these thirty-eight graphs. As a consequence of this, he shows that, for all \(m\geq 3\), an \(m\)-vertex simple planar graph with no \(W_ 6\)-minor has at most \(\lceil (14m-27)/5 \rceil\) edges with this bound being attained for all \(m\).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 429135
zbMATH Keywords: splitter
zbMATH Keywords: 3-connected graph
zbMATH Keywords: wheel
zbMATH Keywords: planar graphs
zbMATH Keywords: minor
reviewed by: James Oxley
MaRDI profile type: Publication
cites work: Q5422499
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: A characterization of 3-connected graphs containing a given graph
cites work: Typical subgraphs of 3- and 4-connected graphs
cites work: The regular matroids with no 5-wheel minor
cites work: Decomposition of regular matroids
cites work: Q3284374
cites work: Q4111952
description: scientific article; zbMATH DE number 429135