A simpler proof of the excluded minor theorem for higher surfaces (Q1362099)

From MaRDI portal
Revision as of 16:53, 27 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
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
    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

    Identifiers