On weighted sublinear separators

Abstract

Consider a graph G with an assignment of costs to vertices. Even if G and all its subgraphs admit balanced separators of sublinear size, G may only admit a balanced separator of sublinear cost after deleting a small set Z of exceptional vertices. We improve the bound on |Z| from O(log |V(G)|) to O(log log...log |V(G)|), for any fixed number of iterations of the logarithm.

arXiv comment14 pages, 0 figures. (v2) Correction to the statement and proof of Theorem 6 (v3) minor changes from reviews after reviews