A note on sublinear separators and expansion

DOI10.1016/J.EJC.2020.103273MaRDI QIDQ2225455zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial expansionsublinear separators

Mathematics Subject Classification ID

Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: For a hereditary class C of graphs, let s_C(n) be the minimum function such that each n-vertex graph in C has a balanced separator of order at most s_C(n), and let nabla_C(r) be the minimum function bounding the expansion of C, in the sense of bounded expansion theory of Nev{s}etv{r}il and Ossona de Mendez. The results of Plotkin, Rao, and Smith (1994) and Esperet and Raymond (2018) imply that if s_C(n)=Theta(n^{1-epsilon}) for some epsilon>0, then nabla_C(r)=Omega(r^{1/(2.epsilon)-1}/polylog r) and nabla_C(r)=O(r^{1/epsilon-1}polylog r). Answering a question of Esperet and Raymond, we show that neither of the exponents can be substantially improved.

Recommendations

• Sublinear separators, fragility and subexponential expansion
• Strongly sublinear separators and polynomial expansion
• Polynomial expansion and sublinear separators
• On classes of graphs with strongly sublinear separators
• Grad and classes with bounded expansion. II: Algorithmic aspects

Cites work

• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Degree-3 treewidth sparsifiers
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph minors. II. Algorithmic aspects of tree-width
• On the separation profile of infinite graphs
• Polynomial expansion and sublinear separators
• Small complete minors above the extremal edge density
• Sparsity. Graphs, structures, and algorithms
• Strongly sublinear separators and polynomial expansion
• The isoperimetric number of random regular graphs
• Treewidth of graphs with balanced separations

Cited in

(7)

• Small graph classes and bounded expansion
• Sublinear separators, fragility and subexponential expansion
• Polynomial expansion and sublinear separators
• Strongly sublinear separators and polynomial expansion
• On classes of graphs with strongly sublinear separators
• Expansion properties for finite subdivision rules. I.
• On weighted sublinear separators

This page was built for publication: A note on sublinear separators and expansion

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