A simpler proof of the excluded minor theorem for higher surfaces (Q1362099)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A simpler proof of the excluded minor theorem for higher surfaces |
scientific article |
Statements
A simpler proof of the excluded minor theorem for higher surfaces (English)
0 references
12 August 1997
0 references
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.
0 references
embedding
0 references
Kuratowski theorem
0 references
surface
0 references
minor
0 references
genus
0 references
grid
0 references