×

Embedding into bipartite graphs. (English) Zbl 1221.05209

Summary: The conjecture of Bollobás and Komlós, recently proved by J. Böttcher, M. Schacht and Taraz [“Proof of the bandwidth conjecture of Bollobás and Komlós,”Math. Ann. 343, No. 1, 175-205 (2009; Zbl 1229.05132)], implies that for any \(\gamma>0\), every balanced bipartite graph on \(2n\) vertices with bounded degree and sublinear bandwidth appears as a subgraph of any \(2n\)-vertex graph \(G\) with minimum degree \((1+\gamma)n\), provided that \(n\) is sufficiently large.
We show that this threshold can be cut in half to an essentially best-possible minimum degree of \((\frac{1}{2}+\gamma)n\) when we have the additional structural information of the host graph \(G\) being balanced bipartite. This complements results of Y. Zhao [“Bipartite graph tiling,” SIAM J. Discrete Math. 23, No.2, 888–900 (2009; Zbl 1191.05075)], as well as J. Hladký and M. Schacht [“Note on bipartite graph tilings,” SIAM J. Discrete Math. 24, No. 2, 357–362 (2010; Zbl 1213.05138)], who determined a corresponding minimum degree threshold for \(K_{r,s}\)-factors, with \(r\) and \(s\) fixed. Moreover, our result can be used to prove that in every balanced bipartite graph \(G\) on \(2n\) vertices with minimum degree \((\frac{1}{2}+\gamma)n\) and \(n\) sufficiently large, the set of Hamilton cycles of \(G\) is a generating system for its cycle space.

MSC:

05C35 Extremal problems in graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv