O(√n) balanced separator for U_t

Open Problem (Section 1): Balanced Separator for $U_t$ · arXiv:2109.00327

arXiv Problem medium confidence— first stated 2021-09-01

Authors: Tony Huynh, Bojan Mohar, Robert Šámal, Carsten Thomassen, David R. Wood

Status open medium confidence

The conjecture asks whether the countable universal graph $U_t$ for $K_t$-minor-free graphs, as constructed in arXiv:2109.00327, satisfies property (K2): every finite $n$-vertex subgraph has a balanced separator of order $O(\sqrt{n})$. The paper itself establishes a weaker $O(n^{3/4}\log n)$ bound from Plotkin–Rao–Smith as the best known result, while proving $U_t$ satisfies properties (K1), (K3), and (K4). A broad search of follow-up literature through May 2026 found no paper resolving or substantially improving upon this open problem.

Reviewer notes. No follow-up resolving (K2) for U_t was found. The paper arXiv:2504.19582 (Faithful universal graphs for minor-closed classes, 2025) addresses polynomial-size universal graphs but resolves different open problems. arXiv:2512.01587 improves the algorithmic runtime for finding O(sqrt(n)) separators in minor-free graphs to linear time but does not address the U_t universal graph question. The weaker O(n^{3/4} log n) bound from Plotkin, Rao, and Smith is the only progress stated in the source paper itself. Confidence is medium rather than high because the conjecture is approximately 5 years old.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. It is open whether $U_t$ satisfies (K2), that is, whether every finite $n$-vertex subgraph of $U_t$ has a balanced separator of order $O(\sqrt{n})$.

Context

Theorem 1.3 constructs, for each $t \in \mathbb{N}$, a countable graph $U_t$ that contains every $K_t$-minor-free graph as an induced subgraph and satisfies properties (K1), (K3), and (K4). Whether $U_t$ also satisfies (K2) (the $O(\sqrt{n})$ balanced separator property shared by planar graphs via the Lipton–Tarjan theorem) remains open. A weaker bound of $O(n^{3/4} \log n)$ on balanced separator size follows from a result of Plotkin, Rao, and Smith.

Notes. Stated as 'It is open whether…' in running prose after Theorem 1.3; no labelled environment. PDF source — math notation appears readable.

Source paper

Universality in minor-closed graph classes
Tony Huynh, Bojan Mohar, Robert Šámal, Carsten Thomassen, David R. Wood · 2021-09-01
https://arxiv.org/abs/2109.00327 PDF source