Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
From MaRDI portal
Publication:976141
DOI10.1016/J.EJC.2009.10.010zbMATH Open1231.05082arXiv0910.3014OpenAlexW2131867452WikidataQ56766816 ScholiaQ56766816MaRDI QIDQ976141FDOQ976141
Klaas P. Pruessmann, Anusch Taraz, Julia Böttcher, Andreas Würfl
Publication date: 17 June 2010
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an expanding subgraph of G. Our results imply that if one of these parameters is sublinear in the number of vertices of G then so are all the others. This implies for example that graphs of fixed genus have sublinear bandwidth or, more generally, a corresponding result for graphs with any fixed forbidden minor. As a consequence we establish a simple criterion for universality for such classes of graphs and show for example that for each gamma>0 every n-vertex graph with minimum degree ((3/4)+gamma)n contains a copy of every bounded-degree planar graph on n vertices if n is sufficiently large.
Full work available at URL: https://arxiv.org/abs/0910.3014
Recommendations
- Bandwidth, treewidth, separators, expansion, and universality
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Bounding the bandwidths for graphs
- On the size of graphs of a given bandwidth
- scientific article; zbMATH DE number 3859182
- scientific article
- Tree-Width and Optimization in Bounded Degree Graphs
- scientific article; zbMATH DE number 894712
- On bandwidth, cutwidth, and quotient graphs
- Large bounded degree trees in expanding graphs
Cites Work
- Embedding large subgraphs into dense graphs
- Title not available (Why is that?)
- On the maximal number of independent circuits in a graph
- Graph minors. XX: Wagner's conjecture
- A partial k-arboretum of graphs with bounded treewidth
- Expander graphs and their applications
- Title not available (Why is that?)
- Some Theorems on Abstract Graphs
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Graph minors. VI. Disjoint paths across a disc
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- Sparse universal graphs for bounded‐degree graphs
- Proof of the bandwidth conjecture of Bollobás and Komlós
- A separator theorem for graphs of bounded genus
- Graph drawings with few slopes
- Large planar subgraphs in dense graphs
- Distinct distances in graph drawings
- On tree width, bramble size, and expansion
- The Blow-up Lemma
- Small universal graphs for bounded-degree planar graphs
Cited In (27)
- Treewidth of graphs with balanced separations
- Planar decompositions and the crossing number of graphs with an excluded minor
- Almost spanning subgraphs of random graphs after adversarial edge removal
- On prisms, Möbius ladders and the cycle space of dense graphs
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Ramsey numbers for bipartite graphs with small bandwidth
- Succinct data structure for path graphs
- Bandwidth theorem for random graphs
- Dominating sets reconfiguration under token sliding
- The bandwidth theorem for locally dense graphs
- Local resilience of spanning subgraphs in sparse random graphs
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- On the bandwidth of the Kneser graph
- Recent progress towards Hadwiger's conjecture
- Universality of random graphs and rainbow embedding
- On the relation of separability, bandwidth and embedding
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Ramsey numbers of cubes versus cliques
- Universal geometric graphs
- On exteriority notions in book embeddings and treewidth
- Forcing spanning subgraphs via Ore type conditions
- Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth
- A tight Erdős-Pósa function for long cycles
- Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
- Ramsey-goodness -- and otherwise
- Embedding Spanning Bipartite Graphs of Small Bandwidth
- Title not available (Why is that?)
This page was built for publication: Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976141)
