Sublinear separators, fragility and subexponential expansion
From MaRDI portal
Publication:896068
DOI10.1016/J.EJC.2015.09.001zbMATH Open1327.05316arXiv1404.7219OpenAlexW2158237076MaRDI QIDQ896068FDOQ896068
Authors: Zdeněk Dvořák 
Publication date: 11 December 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: Let G be a subgraph-closed graph class with bounded maximum degree. We show that if G has balanced separators whose size is smaller than linear by a polynomial factor, then G has subexponential expansion. This gives a partial converse to a result of Nev{s}etv{r}il and Ossona de Mendez. As an intermediate step, the proof uses a new kind of graph decompositions.
Full work available at URL: https://arxiv.org/abs/1404.7219
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- Applications of a Planar Separator Theorem
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- An extremal function for contractions of graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Characterisations and examples of graph classes with bounded expansion
- Graph minors. II. Algorithmic aspects of tree-width
- A Separator Theorem for Planar Graphs
- Sparsity. Graphs, structures, and algorithms
- Topological cliques in graphs II
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Title not available (Why is that?)
- Graph minors. III. Planar tree-width
- Small topological complete subgraphs of ``dense graphs
- The isoperimetric number of random regular graphs
- Title not available (Why is that?)
- Diameter and treewidth in minor-closed graph families
- Kernelization and Sparseness: the case of Dominating Set
- A separator theorem for graphs of bounded genus
- On forbidden subdivision characterizations of graph classes
- Shortest paths in directed planar graphs with negative lengths
- Small graph classes and bounded expansion
- Compact topological minors in graphs
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Planar separators and parallel polygon triangulation.
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Testing first-order properties for subclasses of sparse graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Separator-Based Sparsification II: Edge and Vertex Connectivity
Cited In (11)
- On fractional fragility rates of graph classes
- On classes of graphs with strongly sublinear separators
- Strongly sublinear separators and polynomial expansion
- A note on sublinear separators and expansion
- Colouring strong products
- Uniform local amenability implies property A
- On weighted sublinear separators
- PTAS for Sparse General-valued CSPs
- Polynomial expansion and sublinear separators
- Notes on graph product structure theory
- Bandwidth, treewidth, separators, expansion, and universality
This page was built for publication: Sublinear separators, fragility and subexponential expansion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896068)
