View PDF HTML (experimental)

Abstract:As part of the graph minor project, Robertson and Seymour showed in 1990 that the class of graphs embeddable in a given surface can be characterized by a finite set of minimal excluded minors. However, the proof is purely existential and therefore provides no explicit information about these excluded minors. In 1993, Seymour established the first general upper bound on the order of such minimal excluded minors. Recently, Houdaigoui and Kawarabayashi improved this result by deriving a quasi-polynomial upper bound. Despite this advance, the gap between this bound and the known linear lower bound $\Omega(g)$ (where $g$ denotes the genus) remains substantial. In particular, they conjectured that a polynomial upper bound should hold.
In this paper, we confirm this conjecture by showing that the order of the minimal excluded minors for a surface of genus $g$ is $g^{2+o(1)}$. This result significantly narrows the gap between the known lower and upper bounds, bringing the asymptotic behavior much closer to the conjectured optimum.
Our approach relies on a new structural property of minimal excluded minors. Let $G$ be a minimal excluded minor for a surface of Euler genus $g$. Houdaigoui and Kawarabayashi showed that $G$ contains $O(\log g)$ pairwise disjoint cycles that are contractible and nested in some embedding of $G$. We strengthen this result by proving a separator-based variant: for any contractible subgraph $H \subseteq G$ with a separator of size $s$ (with $H$ contained entirely in one side), the subgraph $H$ contains $O(\log s)$ disjoint cycles that are contractible and nested in some embedding of $G$. This allows us to replace a genus-dependent bound with a separator-dependent one, which is the main new ingredient in deriving our polynomial bound.

Submission history

From: Sarah Houdaigoui [view email]
[v1] Fri, 3 Apr 2026 07:06:32 UTC (76 KB)
[v2] Fri, 4 Sep 2026 07:22:29 UTC (79 KB)