Spanning embeddings of arrangeable graphs with sublinear bandwidth

DOI10.1002/RSA.20593MaRDI QIDQ2795744zbMATH OpenOpenAlexFDO

Authors Julia Böttcher, Anusch Taraz, Andreas Würfl

Publication date 22 March 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2078, http://eprints.lse.ac.uk/65152/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Bottcher%2C%20Julia_Spanning%20embeddings_B%C3%B6ttcher_Spanning%20embeddings_2016.pdf

zbMATH Keywords

arrangeable graphsbandwidth theoremgraph embeddingRamsey numbersregularity method

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: The Bandwidth Theorem of B"ottcher, Schacht and Taraz [Mathematische Annalen 343 (1), 175-205] gives minimum degree conditions for the containment of spanning graphs H with small bandwidth and bounded maximum degree. We generalise this result to a-arrangeable graphs H with Delta(H)<sqrt(n)/log(n), where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least (3/4+gamma)n contain almost all planar graphs on n vertices as subgraphs. Using techniques developed by Allen, Brightwell and Skokan [Combinatorica, to appear] we can also apply our methods to show that almost all planar graphs H have Ramsey number at most 12|H|. We obtain corresponding results for graphs embeddable on different orientable surfaces.

Recommendations

• Embedding spanning subgraphs of small bandwidth
• A spanning bandwidth theorem in random graphs
• The bandwidth theorem in sparse graphs
• Embedding spanning bipartite graphs of small bandwidth
• An extension of the blow-up lemma to arrangeable graphs

Cites work

• An algorithmic version of the blow-up lemma
• An extension of the blow-up lemma to arrangeable graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Blow-up lemma
• Embedding large subgraphs into dense graphs
• Graphs with linearly bounded Ramsey numbers
• scientific article; zbMATH DE number 970807 (Why is no real title available?)
• Large planar subgraphs in dense graphs
• Map-Colour Theorem
• On the maximal number of independent circuits in a graph
• On the Maximum Degree of a Random Planar Graph
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Ramsey-goodness -- and otherwise
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Some Theorems on Abstract Graphs
• Spanning trees in dense graphs
• Spanning triangulations in graphs
• The Blow-up Lemma
• The four-colour theorem

Cited in

(8)

• Embedding spanning subgraphs of small bandwidth
• The bandwidth theorem in sparse graphs
• The bandwidth theorem for locally dense graphs
• An extension of the blow-up lemma to arrangeable graphs
• Bandwidth, treewidth, separators, expansion, and universality
• A spanning bandwidth theorem in random graphs
• Blowing up Dirac's theorem
• Spanning 3-colourable subgraphs of small bandwidth in dense graphs

This page was built for publication: Spanning embeddings of arrangeable graphs with sublinear bandwidth

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