{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:07Z","timestamp":1759063507809},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>Two graphs <jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub> on <jats:italic>n<\/jats:italic> vertices are said to <jats:italic>pack<\/jats:italic> if there exist injective mappings of their vertex sets into [<jats:italic>n<\/jats:italic>] such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollob\u00e1s and Eldridge and, independently, Catlin, asserts that if (\u0394(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>) + 1)(\u0394(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>) + 1) \u2a7d <jats:italic>n<\/jats:italic> + 1, then <jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub> pack. We consider the validity of this assertion under the additional assumption that <jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub> or <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub> has bounded codegree. In particular, we prove for all <jats:italic>t<\/jats:italic> \u2a7e 2 that if <jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub> contains no copy of the complete bipartite graph <jats:italic>K<\/jats:italic><jats:sub>2,<jats:italic>t<\/jats:italic><\/jats:sub> and \u0394(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>) &gt; 17<jats:italic>t<\/jats:italic> \u00b7 \u0394(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>), then (\u0394(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>) + 1)(\u0394(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>) + 1) \u2a7d <jats:italic>n<\/jats:italic> + 1 implies that <jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub> pack. We also provide a mild improvement if moreover <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub> contains no copy of the complete tripartite graph <jats:italic>K<\/jats:italic><jats:sub>1,1,<jats:italic>s<\/jats:italic><\/jats:sub>, <jats:italic>s<\/jats:italic> \u2a7e 1.<\/jats:p>","DOI":"10.1017\/s0963548318000032","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T07:03:07Z","timestamp":1521788587000},"page":"725-740","source":"Crossref","is-referenced-by-count":2,"title":["Packing Graphs of Bounded Codegree"],"prefix":"10.1017","volume":"27","author":[{"given":"WOUTER","family":"CAMES VAN BATENBURG","sequence":"first","affiliation":[]},{"given":"ROSS J.","family":"KANG","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"S0963548318000032_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90005-9"},{"key":"S0963548318000032_ref13","unstructured":"Johansson A. (1996) Asymptotic choice number for triangle-free graphs. Technical report 91-5, DIMACS."},{"key":"S0963548318000032_ref1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-48.1.39"},{"key":"S0963548318000032_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008395"},{"key":"S0963548318000032_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"S0963548318000032_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.05.002"},{"key":"S0963548318000032_ref7","unstructured":"Catlin P. A. (1976) Embedding subgraphs and coloring graphs under extremal degree conditions. PhD thesis, The Ohio State University. ProQuest LLC, Ann Arbor, MI."},{"key":"S0963548318000032_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006887"},{"key":"S0963548318000032_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0013-4"},{"key":"S0963548318000032_ref8","first-page":"159","article-title":"Problem at Schweitzer competition.","volume":"20","author":"Corr\u00e1di","year":"1969","journal-title":"Mat. Lapok"},{"key":"S0963548318000032_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007929"},{"key":"S0963548318000032_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20673"},{"key":"S0963548318000032_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90119-8"},{"key":"S0963548318000032_ref11","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1971"},{"key":"S0963548318000032_ref12","unstructured":"Hajnal A. and Szemer\u00e9di E. (1970) Proof of a conjecture of P. Erd\u0151s. In Combinatorial Theory and its Applications II: (Proc. Colloq., Balatonf\u00fcred, 1969), North-Holland, pp. 601\u2013623."},{"key":"S0963548318000032_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90030-8"},{"key":"S0963548318000032_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2278-0"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T20:50:34Z","timestamp":1555188634000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000032\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S0963548318000032"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000032","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,22]]}}}