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

From MaRDI portal





scientific article; zbMATH DE number 1042501
Language Label Description Also known as
default for all languages
No label defined
    English
    A simpler proof of the excluded minor theorem for higher surfaces
    scientific article; zbMATH DE number 1042501

      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