Hostname: page-component-8448b6f56d-m8qmq Total loading time: 0 Render date: 2024-04-24T22:32:34.176Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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