Embedding spanning bipartite graphs of small bandwidth
From MaRDI portal
Vertex degrees (05C07) 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) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Abstract: Boettcher, Schacht and Taraz gave a condition on the minimum degree of a graph G on n vertices that ensures G contains every r-chromatic graph H on n vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture of Bollobas and Komlos. We strengthen this result in the case when H is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph G on n vertices that forces G to contain every bipartite graph H on n vertices of bounded degree and of bandwidth o(n). This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on G is relaxed to a certain robust expansion property. Our result also confirms the bipartite case of a conjecture of Balogh, Kostochka and Treglown concerning the degree sequence of a graph which forces a perfect H-packing.
Recommendations
Cites work
- \(H\)-factors in dense graphs
- A randomized embedding algorithm for trees
- An approximate version of Sumner's universal tournament conjecture
- An Ore-type theorem for perfect packings in graphs
- An Ore-type theorem on equitable coloring
- Bandwidth theorem for random graphs
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Blow-up lemma
- Forcing spanning subgraphs via Ore type conditions
- Hamiltonian degree sequences in digraphs
- Note on Hamilton Circuits
- On embedding well-separable graphs
- On Hamilton's ideals
- Packing \(d\)-degenerate graphs
- Proof of the Alon-Yuster conjecture
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Proof of the Seymour conjecture for large graphs
- Some Theorems on Abstract Graphs
- The Blow-up Lemma
Cited in
(14)- How tight is the Bollobás-Komlós conjecture?
- Hamilton cycles in sparse robustly expanding digraphs
- On the relation of separability, bandwidth and embedding
- Hamilton decompositions of regular expanders: applications
- A degree sequence Hajnal-Szemerédi theorem
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Embedding spanning subgraphs of small bandwidth
- A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs
- The bandwidth theorem for locally dense graphs
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- On the chromatic number of matching Kneser graphs
- On deficiency problems for graphs
- On sufficient conditions for spanning structures in dense graphs
- Tiling dense hypergraphs (extended abstract)
This page was built for publication: Embedding spanning bipartite graphs of small bandwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903263)
