On weighted sublinear separators
Zdenĕk Dvořák · Journal of Graph Theory · 2021
Abstract Consider a graph with an assignment of costs to vertices. Even if and all its subgraphs admit balanced separators of sublinear size, may only admit a balanced separator of sublinear cost after deleting a small set of exceptional vertices. We improve the bound on from to , for any fixed number of iterations of the logarithm.