Sublinear separators, fragility and subexponential expansion
From MaRDI portal
(Redirected from Publication:896068)
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.
Recommendations
Cites work
- Title not available (Why is no real title available?)
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- A separator theorem for graphs of bounded genus
- An extremal function for contractions of graphs
- Applications of a Planar Separator Theorem
- Approximation algorithms for NP-complete problems on planar graphs
- Characterisations and examples of graph classes with bounded expansion
- Compact topological minors in graphs
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Diameter and treewidth in minor-closed graph families
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. III. Planar tree-width
- Kernelization and Sparseness: the case of Dominating Set
- On forbidden subdivision characterizations of graph classes
- Planar separators and parallel polygon triangulation.
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Small graph classes and bounded expansion
- Small topological complete subgraphs of ``dense graphs
- Sparsity. Graphs, structures, and algorithms
- Testing first-order properties for subclasses of sparse graphs
- The isoperimetric number of random regular graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Topological cliques in graphs II
Cited in
(11)- PTAS for Sparse General-valued CSPs
- Colouring strong products
- On fractional fragility rates of graph classes
- Notes on graph product structure theory
- A note on sublinear separators and expansion
- Uniform local amenability implies property A
- Polynomial expansion and sublinear separators
- Bandwidth, treewidth, separators, expansion, and universality
- Strongly sublinear separators and polynomial expansion
- On classes of graphs with strongly sublinear separators
- On weighted sublinear separators
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)
