Embedding spanning bipartite graphs of small bandwidth

DOI10.1017/S0963548312000417MaRDI QIDQ4903263zbMATH OpenOpenAlexFDO

Authors Fiachra Knox, Andrew Treglown

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) 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)

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

• 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

Cites work

• A randomized embedding algorithm for trees
• An Ore-type theorem for perfect packings in graphs
• An Ore-type theorem on equitable coloring
• An approximate version of Sumner's universal tournament conjecture
• 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 Hamilton's ideals
• On embedding well-separable graphs
• Packing \(d\)-degenerate graphs
• Proof of the Alon-Yuster conjecture
• Proof of the Seymour conjecture for large graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Some Theorems on Abstract Graphs
• The Blow-up Lemma
• \(H\)-factors in dense graphs

Cited in

(12)

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