A Kuratowski theorem for nonorientable surfaces
type: Item
instance of: scholarly article
title: A Kuratowski theorem for nonorientable surfaces
zbMATH Open document ID: 0616.05034
DOI: 10.1016/0095-8956(89)90043-9
author: Phil Huneke
author: Dan S. Archdeacon
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: Let \(\Sigma\) denote a surface. A graph G is irreducible for \(\Sigma\) provided that G does not embed in \(\Sigma\), but any proper subgraph does so embed. Let I(\(\Sigma)\) denote the set of graphs without degree two vertices which are irreducible for \(\Sigma\). Observe that a graph embeds in \(\Sigma\) if and only if it does not contain a subgraph homeomorphic to a member of I(\(\Sigma)\). For example, Kuratowski's theorem shows that \(I(\Sigma)=\{K_{3,3},K_ 5\}\) when \(\Sigma\) is the sphere. In this paper we prove that the set I(\(\Sigma)\) is finite for each nonorientable surface, settling in part a conjecture of Erdős from the 1930's.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3997828
zbMATH Keywords: irreducible graphs
MaRDI profile type: Publication
full work available at URL: 0095-8956(89)90043-9
OpenAlex ID: W2005856488
cites work: A kuratowski theorem for the projective plane
cites work: On cubic graphs which are irreducible for nonorientable surfaces
cites work: Additivity of the genus of a graph
cites work: Cubic irreducible graphs for the projective plane
cites work: Graphs with bounded valency that do not embed in the projective plane
cites work: The set of irreducible graphs for the projective plane is finite
cites work: 103 graphs that are irreducible for the projective plane
cites work: Q4187845
cites work: Irreducible graphs
cites work: Irreducible graphs. II
cites work: Graph minors. VIII: A Kuratowski theorem for general surfaces
cites work: Q3222217
cites work: Q3684139
cites work: Generalized Embedding Schemes
cites work: Blocks and the nonorientable genus of graphs
cites work: Q3847965
description: scientific article; zbMATH DE number 3997828