Embedding Spanning Bipartite Graphs of Small Bandwidth

DOI10.1017/S0963548312000417zbMath1257.05071arXiv1111.4292OpenAlexW2106107541MaRDI QIDQ4903263

Andrew Treglown, Fiachra Knox

Publication date: 21 January 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

minimum degree of a graphdegree sequence of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Vertex degrees (05C07) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (10)

Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ On deficiency problems for graphs ⋮ A Degree Sequence Strengthening of the Vertex Degree Threshold for a Perfect Matching in 3-Uniform Hypergraphs ⋮ Hamilton cycles in sparse robustly expanding digraphs ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ Hamilton decompositions of regular expanders: applications ⋮ The bandwidth theorem for locally dense graphs ⋮ On the relation of separability, bandwidth and embedding ⋮ On the Chromatic Number of Matching Kneser Graphs ⋮ A degree sequence Hajnal-Szemerédi theorem

Cites Work

• A randomized embedding algorithm for trees
• An approximate version of Sumner's universal tournament conjecture
• Bandwidth theorem for random graphs
• On embedding well-separable graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Hamiltonian degree sequences in digraphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• \(H\)-factors in dense graphs
• Packing \(d\)-degenerate graphs
• An Ore-type theorem on equitable coloring
• On Hamilton's ideals
• Forcing spanning subgraphs via Ore type conditions
• Note on Hamilton Circuits
• An Ore-type Theorem for Perfect Packings in Graphs
• The Blow-up Lemma
• Some Theorems on Abstract Graphs
• Proof of the Alon-Yuster conjecture

This page was built for publication: Embedding Spanning Bipartite Graphs of Small Bandwidth