A Simpler Proof of the Excluded Minor Theorem for Higher Surfaces |
| |
Authors: | Carsten Thomassen |
| |
Affiliation: | Mathematical Institute, Technical University of Denmark, DK-2800, Lyngby, Denmark |
| |
Abstract: | We give a simple proof of the fact (which follows from the Robertson–Seymour theory) that a graph which is minimal of genusgcannot contain a subdivision of a large grid. Combining this with the tree-width theorem and the quasi-wellordering of graphs of bounded tree-width in the Robertson–Seymour theory, we obtain a simpler proof of the generalized Kuratowski theorem for each fixed surface. The proof requires no previous knowledge of graph embeddings. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|