{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:48:22Z","timestamp":1787507302426,"version":"build-2736575974"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2012,10,3]],"date-time":"2012-10-03T00:00:00Z","timestamp":1349222400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>\n                    B\u00f6ttcher, Schacht and Taraz (\n                    <jats:italic>Math. Ann.<\/jats:italic>\n                    , 2009) gave a condition on the minimum degree of a graph\n                    <jats:italic>G<\/jats:italic>\n                    on\n                    <jats:italic>n<\/jats:italic>\n                    vertices that ensures\n                    <jats:italic>G<\/jats:italic>\n                    contains every\n                    <jats:italic>r<\/jats:italic>\n                    -chromatic graph\n                    <jats:italic>H<\/jats:italic>\n                    on\n                    <jats:italic>n<\/jats:italic>\n                    vertices of bounded degree and of bandwidth\n                    <jats:italic>o<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ), thereby proving a conjecture of Bollob\u00e1s and Koml\u00f3s (\n                    <jats:italic>Combin. Probab. Comput.<\/jats:italic>\n                    , 1999). We strengthen this result in the case when\n                    <jats:italic>H<\/jats:italic>\n                    is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph\n                    <jats:italic>G<\/jats:italic>\n                    on\n                    <jats:italic>n<\/jats:italic>\n                    vertices that forces\n                    <jats:italic>G<\/jats:italic>\n                    to contain every bipartite graph\n                    <jats:italic>H<\/jats:italic>\n                    on\n                    <jats:italic>n<\/jats:italic>\n                    vertices of bounded degree and of bandwidth\n                    <jats:italic>o<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ). This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on\n                    <jats:italic>G<\/jats:italic>\n                    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\n                    <jats:italic>H<\/jats:italic>\n                    -packing.\n                  <\/jats:p>","DOI":"10.1017\/s0963548312000417","type":"journal-article","created":{"date-parts":[[2012,10,3]],"date-time":"2012-10-03T08:05:23Z","timestamp":1349251523000},"page":"71-96","source":"Crossref","is-referenced-by-count":10,"title":["Embedding Spanning Bipartite Graphs of Small Bandwidth"],"prefix":"10.1017","volume":"22","author":[{"given":"FIACHRA","family":"KNOX","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ANDREW","family":"TREGLOWN","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,10,3]]},"reference":[{"key":"S0963548312000417_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.11.004"},{"key":"S0963548312000417_ref25","doi-asserted-by":"publisher","DOI":"10.1137\/080731256"},{"key":"S0963548312000417_ref28","first-page":"201","volume-title":"Combinatorics: Proceedings of the British Combinatorial Conference 1973","author":"Seymour","year":"1974"},{"key":"S0963548312000417_ref23","doi-asserted-by":"crossref","unstructured":"K\u00fchn D. and Osthus D. (2006) Critical chromatic number and the complexity of perfect packings in graphs. In 17th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 851\u2013859.","DOI":"10.1145\/1109557.1109651"},{"key":"S0963548312000417_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"S0963548312000417_ref15","unstructured":"H\u00e0n H. (2006) Einbettungen bipartiter Graphen mit kleiner Bandbreite. Master's thesis, Humboldt-Universit\u00e4t zu Berlin, Institut f\u00fcr Informatik."},{"key":"S0963548312000417_ref13","unstructured":"Erd\u0151s P. (1964) Problem 9. In Theory of Graphs and its Applications ( M. Fieldler , ed.), Czech. Acad. Sci. Publ., p. 159."},{"key":"S0963548312000417_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895727"},{"key":"S0963548312000417_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.07.003"},{"key":"S0963548312000417_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90020-2"},{"key":"S0963548312000417_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"},{"key":"S0963548312000417_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.11.005"},{"key":"S0963548312000417_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.10.010"},{"key":"S0963548312000417_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.002"},{"key":"S0963548312000417_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.12.006"},{"key":"S0963548312000417_ref14","first-page":"601","volume-title":"Combinatorial Theory and its Applications II","author":"Hajnal","year":"1970"},{"key":"S0963548312000417_ref3","unstructured":"B\u00f6ttcher J. (2009) Embedding large graphs: The Bollob\u00e1s\u2013Koml\u00f3s conjecture and beyond. PhD thesis, Technische Universit\u00e4t M\u00fcnchen."},{"key":"S0963548312000417_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0020"},{"key":"S0963548312000417_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01626028"},{"key":"S0963548312000417_ref12","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548312000417_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00279-X"},{"key":"S0963548312000417_ref8","unstructured":"Ch\u00e2u P. An Ore-type theorem on Hamiltonian square cycles. Graphs Combin., to appear."},{"key":"S0963548312000417_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003502"},{"key":"S0963548312000417_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"},{"key":"S0963548312000417_ref27","doi-asserted-by":"publisher","DOI":"10.2307\/2308928"},{"key":"S0963548312000417_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2422-5"},{"key":"S0963548312000417_ref30","unstructured":"Szemer\u00e9di E. (1978) Regular partitions of graphs. In Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399\u2013401."},{"key":"S0963548312000417_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.015"},{"key":"S0963548312000417_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2009.07.042"},{"key":"S0963548312000417_ref2","unstructured":"Balogh J. , Kostochka A. V. and Treglown A. On perfect packings in dense graphs. Submitted."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T16:05:57Z","timestamp":1556121957000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000417\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0963548312000417"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000417","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,3]]}}}