Constant-size separator M in bounded expansion
Informal Conjecture (constant-size M) · arXiv:1710.03117
Status open medium confidence
No published paper resolving this conjecture was found. Dvořák's 2022 Journal of Graph Theory paper 'On weighted sublinear separators' is a likely follow-up, but its full content is behind a paywall and could not be verified. The conjecture that the polylogarithmic-in-n bound on |M| in the weighted balanced separator C∪M can be replaced by a constant depending only on the graph class and ℓ remains, as far as can be determined from open-access sources, open.
Reviewer notes. Dvořák published a follow-up paper 'On weighted sublinear separators' in J. Graph Theory 2022 (DOI 10.1002/jgt.22777) which may address this conjecture, but the paper is paywalled and the abstract does not explicitly mention the constant-size M conjecture. The 2022 paper 'Product Structure of Graph Classes with Strongly Sublinear Separators' (arXiv:2208.10074) and the 2026 paper 'Coarse Balanced Separators in Fat-Minor-Free Graphs' (arXiv:2604.11318) do not appear to reference this specific conjecture. Confidence is medium rather than high because the conjecture is ~8 years old and a relevant paywalled paper could not be fully verified.
Context
Theorem 5 guarantees a weighted balanced separator $C \cup M$ with $q(C) \leq q(V(G))/\ell$, but the bound on $|M|$ is only polylogarithmic in $n$ for graphs from a class with polynomial $\omega$-expansion. The author conjectures this polylogarithmic dependence on $n$ can be eliminated entirely, yielding a set $M$ of size depending only on the graph class and $\ell$.
Notes. Stated as inline prose in the bullet-point remarks following Theorem 5; no labelled theorem environment.
Source paper
On classes of graphs with strongly sublinear separators
Zdeněk Dvořák · 2018-02-09
https://arxiv.org/abs/1710.03117
PDF source