On weighted sublinear separators

DOI10.1002/JGT.22777MaRDI QIDQ6081561zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11853

zbMATH Keywords

polynomial expansionseparators

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• Weighted estimates for a class of sublinear operators
• On the netweight of subspaces
• scientific article; zbMATH DE number 810367
• A note on sublinear separators and expansion
• scientific article; zbMATH DE number 822110
• Weighted estimates for the multisublinear maximal function
• scientific article; zbMATH DE number 1553330
• Weighted graph separators and their applications
• scientific article; zbMATH DE number 721735
• On weighted \(L^p\) simultaneous approximation

Cites work

• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for polynomial-expansion and low-density graphs
• Coloring and covering nowhere dense graphs
• Constant-factor approximation of the domination number in sparse graphs
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Geometric Separators for Finite-Element Meshes
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• On classes of graphs with strongly sublinear separators
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Polynomial expansion and sublinear separators
• Separators for sphere-packings and nearest neighbor graphs
• Strongly sublinear separators and polynomial expansion
• Sublinear separators, fragility and subexponential expansion

Cited in

(3)

• MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
• A color-avoiding approach to subgraph counting in bounded expansion classes
• Product structure of graph classes with strongly sublinear separators

This page was built for publication: On weighted sublinear separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081561)