On the relation of separability, bandwidth and embedding

DOI10.1007/S00373-019-02086-3MaRDI QIDQ2287746zbMATH OpenOpenAlexWikidataFDO

Authors Bálint Vásárhelyi, Béla Csaba

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bandwidthextremal graph theoryseparability

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper we construct a class of bounded degree bipartite graphs with a small separator and large bandwidth. Furthermore, we also prove that graphs from this class are spanning subgraphs of graphs with minimum degree just slightly larger than $n/2$.

Recommendations

• Bandwidth, treewidth, separators, expansion, and universality
• On embedding well-separable graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Edge Separators of Planar and Outerplanar Graphs With Applications
• A spectral approach to bandwidth and separator problems in graphs

Cites work

• A bandwidth theorem for approximate decompositions
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Blow-up lemma
• Dependent random choice
• Embedding Arbitrary Graphs of Maximum Degree Two
• Embedding spanning bipartite graphs of small bandwidth
• Explicit constructions of graphs without short cycles and low density codes
• How tight is the Bollobás-Komlós conjecture?
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Lower bounds of tower type for Szemerédi's uniformity lemma
• On a graph packing conjecture by Bollobás, Eldridge and Catlin
• On degree sequences forcing the square of a Hamilton cycle
• On embedding well-separable graphs
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs
• Packings of graphs and applications to computational complexity
• Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Ramanujan graphs
• Some Theorems on Abstract Graphs
• The Blow-up Lemma
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(2)

• How many steps are necessary to separate a bigraph?
• Bandwidth, treewidth, separators, expansion, and universality

This page was built for publication: On the relation of separability, bandwidth and embedding

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