K h-Minor-Free Graphs Have Balanced Separators of Size O(h sqrt n)

arXiv:2611.00663 · math.CO, cs.DM · Submitted 2026-10-31 · Read on arXiv

math.CO, cs.DM

Submitted: 2026-10-31

Updated: 2026-10-31

Code: https://github.com/jacketsj/formalized-minor-free-separators

License: http://creativecommons.org/licenses/by/4.0/

The gist: We show that every K h-minor-free graph with n vertices has a balanced separator of size O(h sqrt n) for any parameter h in N, resolving the conjecture posed by Alon, Seymour…

Abstract

We show that every K h-minor-free graph with n vertices has a balanced separator of size O(h sqrt n) for any parameter h in N, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given k large (not necessarily disjoint) subsets of vertices, there is a walk of length O(k/ψ(G)) hitting every subset, where ψ(G) is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

Sources

Related papers