Embedding Spanning Bipartite Graphs of Small Bandwidth
From MaRDI portal
Publication:4903263
DOI10.1017/S0963548312000417zbMath1257.05071arXiv1111.4292MaRDI QIDQ4903263
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
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