PreprintCC BY 4.0arXiv
Kh-Minor-Free Graphs Have Balanced Separators of Size O(h√n)
Abstract
We show that every Kh-minor-free graph with n vertices has a balanced separator of size O(h√n) for any parameter h ∈ ℕ, 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.
Related
- On separators in Kt-minor-free graphs
- Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
- Coloring Small Kt-Minor-Free Graphs
- A note on highly connected K2,ℓ -minor free graphs
- On the maximum degree and order of Kt-minor-free graphs with positive Lin--Lu--Yau curvature
BibTeX
@misc{conroy2026khminorfree,
title = {{$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrtn)$}},
author = {Jonathan Conroy and Hung Le and Jack Spalding-Jamieson},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00663},
eprint = {2611.00663},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00663},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - K_h-Minor-Free Graphs Have Balanced Separators of Size O(h√n)
AU - Jonathan Conroy
AU - Hung Le
AU - Jack Spalding-Jamieson
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00663
UR - https://arxiv.org/abs/2611.00663
AB - We show that every K_h-minor-free graph with n vertices has a balanced separator of size O(h√n) for any parameter h ∈ ℕ, 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.
ER -