A quasi-polynomial bound for the minimal excluded minors for a surface
Preprint
Abstract
As part of their graph minor project, Robertson and Seymour showed in 1990 that the class of graphs that can be embedded in a given surface can be characterized by a finite set of minimal excluded minors. However, their proof, because existential, does not provide any information on these excluded minors. Seymour proved in 1993 the first and, until now, only known upper bound on the order of the minimal excluded minors for a given surface. This bound is double exponential in the Euler genus $g$ of the surface and, therefore, very far from the $Ω(g)$ lower bound on the maximal order of minimal excluded minors for a surface and most likely far from the best possible bound. More than thirty years later, this paper finally makes progress in lowering this bound to a quasi-polynomial in the Euler genus of the surface. The main catalyzer to reach a quasi-polynomial bound is a breakthrough on the characteristic size of a forbidden structure for a minimal excluded minor $G$ for a surface of Euler genus $g$: although it is not hard to show that $G$ does not contain $O(g)$ disjoint cycles that are contractible and nested in some embedding of $G$ as demonstrated by Seymour, this bound can be lowered to $O(\log g)$ which is essential to obtain the quasi-polynomial bound in this paper. As subsidiary results, we also improve the current bound on the treewidth of a minimal excluded minor $G$ for a surface by improving the first and, until now, only known bound provided by Seymour.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- A Simpler Proof of the Excluded Minor Theorem for Higher SurfacesJournal of Combinatorial Theory, Series B, 1997
- Uniqueness of highly representative surface embeddingsJournal of Graph Theory, 1996
- Uniqueness and minimality of large face-width embeddings of graphsCombinatorica, 1995
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Minimal acyclic forbidden minors for the family of graphs with bounded path-widthDiscrete Mathematics, 1994
- The vertex separation number of a graph equals its path-widthInformation Processing Letters, 1992
- A kuratowski theorem for the projective planeJournal of Graph Theory, 1981
- 103 Graphs that are irreducible for the projective planeJournal of Combinatorial Theory, Series B, 1979
- The set of irreducible graphs for the projective plane is finiteDiscrete Mathematics, 1978
- The genus of subgraphs ofK 8Israel Journal of Mathematics, 1972