Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-11T20:24:58.912Z Has data issue: false hasContentIssue false
  • English
  • Français

Embedding Spanning Bipartite Graphs of Small Bandwidth

Published online by Cambridge University Press:  03 October 2012

FIACHRA KNOX  and
ANDREW TREGLOWN
FIACHRA KNOX
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: knoxf@maths.bham.ac.uk)
ANDREW TREGLOWN
Affiliation:
Faculty of Mathematics and Physics, Charles University, Malostranské Náměstí 25, 188 00 Prague, Czech Republic (e-mail: treglown@kam.mff.cuni.cz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Böttcher, Schacht and Taraz (Math. Ann., 2009) 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 Bollobás and Komlós (Combin. Probab. Comput., 1999). 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.

Keywords

Primary 05C35Secondary 05C7005C7805D40
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 1 , January 2013 , pp. 71 - 96
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N. and Yuster, R. (1996) H-factors in dense graphs. J. Combin. Theory Ser. B 66 269–282.Google Scholar
[2]Balogh, J., Kostochka, A. V. and Treglown, A. On perfect packings in dense graphs. Submitted.Google Scholar
[3]Böttcher, J. (2009) Embedding large graphs: The Bollobás–Komlós conjecture and beyond. PhD thesis, Technische Universität München.Google Scholar
[4]Böttcher, J. and Müller, S. (2009) Forcing spanning subgraphs via Ore type conditions, Electron. Notes Discrete Math. 34 255–259.Google Scholar
[5]Böttcher, J., Preussmann, K., Taraz, A. and Würfl, A. (2010) Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. Europ. J. Combin. 31 1217–1227.CrossRefGoogle Scholar
[6]Böttcher, J., Schacht, M. and Taraz, A. (2008) Spanning 3-colourable subgraphs of small bandwidth in dense graphs. J. Combin. Theory Ser. B 98 85–94.Google Scholar
[7]Böttcher, J., Schacht, M. and Taraz, A. (2009) Proof of the bandwidth conjecture of Bollobás and Komlós. Math. Ann. 343 175–205.Google Scholar
[8]Châu, P. An Ore-type theorem on Hamiltonian square cycles. Graphs Combin., to appear.Google Scholar
[9]Chvátal, V. (1972) On Hamilton's ideals. J. Combin. Theory Ser. B 12 163–168.Google Scholar
[10]Corrádi, K. and Hajnal, A. (1964) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.Google Scholar
[11]Csaba, B. (2008) On embedding well-separable graphs. Discrete Math. 308 4322–4331.Google Scholar
[12]Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 2 69–81.Google Scholar
[13]Erdős, P. (1964) Problem 9. In Theory of Graphs and its Applications (Fieldler, M., ed.), Czech. Acad. Sci. Publ., p. 159.Google Scholar
[14]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of Erdős. In Combinatorial Theory and its Applications II, North-Holland, pp. 601–623.Google Scholar
[15]Hàn, H. (2006) Einbettungen bipartiter Graphen mit kleiner Bandbreite. Master's thesis, Humboldt-Universität zu Berlin, Institut für Informatik.Google Scholar
[16]Huang, H., Lee, C. and Sudakov, B. (2012) Bandwidth theorem for random graphs. J. Combin. Theory Ser. B 102 14–37.Google Scholar
[17]Kierstead, H. A. and Kostochka, A. V. (2008) An Ore-type theorem on equitable coloring. J. Combin. Theory Ser. B 98 226–234.Google Scholar
[18]Komlós, J. (1999) The blow-up lemma. Combin. Probab. Comput. 8 161–176.CrossRefGoogle Scholar
[19]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-up lemma. Combinatorica 17 109–123.Google Scholar
[20]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1998) Proof of the Seymour conjecture for large graphs. Ann. Combin. 2 43–60.Google Scholar
[21]Komlós, J., Sárközy, G. N. and Szemerédi, E. (2001) Proof of the Alon–Yuster conjecture. Discrete Math. 235 255–269.Google Scholar
[22]Kühn, D., Mycroft, R. and Osthus, D. (2011) An approximate version of Sumner's universal tournament conjecture. J. Combin. Theory Ser. B 101 415–447.Google Scholar
[23]Kühn, D. and Osthus, D. (2006) Critical chromatic number and the complexity of perfect packings in graphs. In 17th ACM–SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 851–859.Google Scholar
[24]Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.Google Scholar
[25]Kühn, D., Osthus, D. and Treglown, A. (2009) An Ore-type theorem for perfect packings in graphs. SIAM J. Discrete Math. 23 1335–1355.Google Scholar
[26]Kühn, D., Osthus, D. and Treglown, A. (2010) Hamiltonian degree sequences in digraphs. J. Combin. Theory Ser. B 100 367–380.Google Scholar
[27]Ore, O. (1960) Note on Hamilton circuits. Amer. Math. Monthly 67 55.Google Scholar
[28]Seymour, P. (1974) Problem section. In Combinatorics: Proceedings of the British Combinatorial Conference 1973 (McDonough, T. P. and Mavron, V. C., eds), Cambridge University Press, pp. 201–202.Google Scholar
[29]Sudakov, B. and Vondrak, J. (2010) A randomized embedding algorithm for trees. Combinatorica 30 445–470.Google Scholar
[30]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399–401.Google Scholar