Spanning embeddings of arrangeable graphs with sublinear bandwidth

DOI10.1002/rsa.20593zbMath1332.05097arXiv1305.2078OpenAlexW2118745698MaRDI QIDQ2795744

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

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

zbMATH Keywords

Ramsey numbersgraph embeddingregularity methodarrangeable graphsbandwidth theorem

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)

Related Items

The bandwidth theorem for locally dense graphs ⋮ An Extension of the Blow-up Lemma to Arrangeable Graphs

Cites Work

• Unnamed Item
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• The four-colour theorem
• Blow-up lemma
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Ramsey-goodness -- and otherwise
• Graphs with linearly bounded Ramsey numbers
• Large planar subgraphs in dense graphs
• Spanning Trees in Dense Graphs
• On the Maximum Degree of a Random Planar Graph
• Embedding large subgraphs into dense graphs
• An algorithmic version of the blow-up lemma
• The Blow-up Lemma
• An Extension of the Blow-up Lemma to Arrangeable Graphs
• Spanning triangulations in graphs
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• On the maximal number of independent circuits in a graph
• Map-Colour Theorem
• Some Theorems on Abstract Graphs