Premium
On weighted sublinear separators
Author(s) -
Dvořák Zdeněk
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22777
Subject(s) - sublinear function , mathematics , combinatorics , logarithm , separator (oil production) , graph , discrete mathematics , upper and lower bounds , mathematical analysis , physics , thermodynamics
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.