$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$
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 \mathbb{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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.00663
curl -X POST /api/v1/records/arxiv/2611.00663/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.00663/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'