Polynomial expansion and sublinear separators

DOI10.1016/J.EJC.2017.09.003MaRDI QIDQ1686248zbMATH OpenOpenAlexFDO

Authors L. Esperet, Jean-Florent Raymond

Publication date 21 December 2017

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

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

zbMATH Keywords

polynomial expansionsublinear separators

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Connectivity (05C40) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: Let $mathcalC$ be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed $0<deltale1$, every $n$-vertex graph of $mathcalC$ has a balanced separator of order $O(n^{1-delta})$, then any depth-$k$ minor (i.e. minor obtained by contracting disjoint subgraphs of radius at most $k$) of a graph in $mathcalC$ has average degree $$. This confirms a conjecture of Dvov{r}'ak and Norin.

Recommendations

• Sublinear separators, fragility and subexponential expansion
• A note on sublinear separators and expansion
• Strongly sublinear separators and polynomial expansion
• Minors in expanding graphs
• On classes of graphs with strongly sublinear separators

Cites work

• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Degree-3 treewidth sparsifiers
• Large-treewidth graph decompositions and applications
• Small complete minors above the extremal edge density
• Sparsity. Graphs, structures, and algorithms
• Strongly sublinear separators and polynomial expansion

Cited in

(13)

• On subwords in the base-$q$ expansion of polynomial and exponential functions
• scientific article; zbMATH DE number 5263329 (Why is no real title available?)
• Sublinear separators in intersection graphs of convex shapes
• Notes on graph product structure theory
• On subword decomposition and balanced polynomials
• Sublinear separators, fragility and subexponential expansion
• Improved bounds for weak coloring numbers
• A note on sublinear separators and expansion
• Sparse graphs without long induced paths
• Coloring and covering nowhere dense graphs
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• Strongly sublinear separators and polynomial expansion
• On weighted sublinear separators

This page was built for publication: Polynomial expansion and sublinear separators

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