K h-Minor-Free Graphs Have Balanced Separators of Size O(h sqrt n)
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
- Coarse Balanced Separators in Fat-Minor-Free Graphs
- A Separator for Minor-Free Graphs Beyond the Flow Barrier
- Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality