On weighted sublinear separators

DOI10.1002/JGT.22777zbMATH Open1522.05246arXiv2007.11853OpenAlexW3215408592MaRDI QIDQ6081561FDOQ6081561

Authors: Zdeněk Dvořák 

Publication date: 5 October 2023

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

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.

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

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

zbMATH Keywords

separatorspolynomial expansion

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• A color-avoiding approach to subgraph counting in bounded expansion classes
• MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS

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)