Embedding spanning bipartite graphs of small bandwidth

DOI10.1017/S0963548312000417zbMATH Open1257.05071arXiv1111.4292OpenAlexW2106107541MaRDI QIDQ4903263FDOQ4903263

Authors: Fiachra Knox, Andrew Treglown 

Publication date: 21 January 2013

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

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.

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

Recommendations

• Embedding spanning subgraphs of small bandwidth
• Embedding into Bipartite Graphs
• How tight is the Bollobás-Komlós conjecture?
• On the bandwidth conjecture for \(3\)-colourable graphs
• Forcing spanning subgraphs via Ore type conditions

zbMATH Keywords

minimum degree of a graphdegree sequence of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) 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)

Cites Work

• On Hamilton's ideals
• Proof of the Seymour conjecture for large graphs
• \(H\)-factors in dense graphs
• An Ore-type theorem on equitable coloring
• An Ore-type theorem for perfect packings in graphs
• Proof of the Alon-Yuster conjecture
• Note on Hamilton Circuits
• Some Theorems on Abstract Graphs
• Blow-up lemma
• Bandwidth theorem for random 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
• The Blow-up Lemma
• An approximate version of Sumner's universal tournament conjecture
• A randomized embedding algorithm for trees
• On embedding well-separable graphs
• Packing \(d\)-degenerate graphs
• Forcing spanning subgraphs via Ore type conditions

Cited In (12)

• Hamilton decompositions of regular expanders: applications
• A degree sequence Hajnal-Szemerédi theorem
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs
• Embedding spanning subgraphs of small bandwidth
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• The bandwidth theorem for locally dense graphs
• On deficiency problems for graphs
• On the chromatic number of matching Kneser graphs
• Hamilton cycles in sparse robustly expanding digraphs
• On the relation of separability, bandwidth and embedding
• On sufficient conditions for spanning structures in dense graphs

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)