Embedding Spanning Bipartite Graphs of Small Bandwidth

DOI10.1017/S0963548312000417zbMath1257.05071arXiv1111.4292MaRDI 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 graph; degree sequence of a graph

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C07: Vertex degrees

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

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

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