A simpler proof of the excluded minor theorem for higher surfaces
type: Item
instance of: scholarly article
title: A simpler proof of the excluded minor theorem for higher surfaces
zbMATH Open document ID: 0882.05053
author: Carsten Thomassen
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-08-12T00:00:00Z
review text: The paper offers a shorter proof of the Kuratowski theorem for higher surfaces: for any closed surface \(S\) there exist graphs \(G_1,G_2,\dots,G_m\) such that a graph \(G\) is embeddable in \(S\) if and only if none of \(G_1,G_2,\dots,G_m\) is contained in \(S\) as a minor. This theorem was conjectured in the 1930s by Erdös and König and its general case was eventually established by \textit{N. Robertson} and \textit{P. D. Seymour} in [J. Comb. Theory, Ser. B 48, No. 2, 255-288 (1990; Zbl 0719.05033)]. The new proof consists in providing a short proof of the fact (which follows from the Robertson and Seymour theory) that a minimal graph of genus \(g\) cannot contain a subdivision of a large grid.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1042501
zbMATH Keywords: embedding
zbMATH Keywords: Kuratowski theorem
zbMATH Keywords: surface
zbMATH Keywords: minor
zbMATH Keywords: genus
zbMATH Keywords: grid
reviewed by: Martin Škoviera
MaRDI profile type: Publication
full work available at URL: jctb.1997.1761
OpenAlex ID: W2028348726
cites work: A Kuratowski theorem for nonorientable surfaces
cites work: Additivity of the genus of a graph
cites work: Solution to König's Graph Embedding Problem
cites work: The genus of the 2-amalgamations of graphs
cites work: Combinatorial Local Planarity and the Width of Graph Embeddings
cites work: Graphs on surfaces
cites work: Graph minors. IV: Tree-width and well-quasi-ordering
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. VIII: A Kuratowski theorem for general surfaces
cites work: Embeddings of graphs with no short noncontractible cycles
cites work: Q4871753
DOI: 10.1006/JCTB.1997.1761
description: scientific article; zbMATH DE number 1042501