An Extension of the Blow-up Lemma to Arrangeable Graphs

DOI10.1137/13093827XzbMath1314.05133arXiv1305.2059OpenAlexW1512971738WikidataQ105584178 ScholiaQ105584178MaRDI QIDQ5254090

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

Publication date: 8 June 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

regularity lemmaspanning subgraphsgraph embeddingsblow-up lemmaarrangeable graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Monochromatic cycle power partitions ⋮ Maximum planar subgraphs in dense graphs ⋮ On Degree Sequences Forcing The Square of a Hamilton Cycle ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Spanning embeddings of arrangeable graphs with sublinear bandwidth ⋮ Monochromatic square-cycle and square-path partitions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum planar subgraphs in dense graphs
• Bandwidth theorem for random graphs
• The Ramsey number of a graph with bounded maximum degree
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• Tiling Turán theorems
• \(H\)-factors in dense graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• The minimum degree threshold for perfect graph packings
• Graphs with linearly bounded Ramsey numbers
• Large planar subgraphs in dense graphs
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• Embedding large subgraphs into dense graphs
• An algorithmic version of the blow-up lemma
• The Blow-up Lemma
• Spanning Subgraphs of Random Graphs
• An Algorithmic Regularity Lemma for Hypergraphs
• Proof of a Packing Conjecture of Bollobás
• On the square of a Hamiltonian cycle in dense graphs
• On Equitable Coloring of d-Degenerate Graphs
• Sparse universal graphs for bounded‐degree graphs
• Spanning triangulations in graphs
• Proof of the Alon-Yuster conjecture

This page was built for publication: An Extension of the Blow-up Lemma to Arrangeable Graphs