On two conjectures on packing of graphs

Béla Bollobás, Alexandr Kostochka, Kittikorn Nakprasit

Research output: Contribution to journalArticlepeer-review


In 1978, Bollobás and Eldridge [5] made the following two conjectures.(C1) There exists an absolute constant c > 0 such that, if k is a positive integer and $G_1$ and $G_2$ are graphs of order n such that $\Delta(G_1),\Delta(G_2)\leq n-k$ and $e(G_1),e(G_2)\leq ck n$, then the graphs $G_1$ and $G_2$ pack. (C2) For all $0 and $0, there exists an $n_0=n_0(\alpha,c)$ such that, if $G_1$ and $G_2$ are graphs of order n > n0 satisfying $e(G_1)\leq \alpha n$ and e(G2)≤ c√ n 3\alpha, then the graphs $G_1$ and $G_2$ pack. Conjecture (C2) was proved by Brandt [6]. In the present paper we disprove (C1) and prove an analogue of (C2) for $1/2\leq \alpha. We also give sufficient conditions for simultaneous packings of about √n/4 sparse graphs.

Original languageEnglish (US)
Pages (from-to)723-736
Number of pages14
JournalCombinatorics Probability and Computing
Issue number5-6
StatePublished - Nov 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On two conjectures on packing of graphs'. Together they form a unique fingerprint.

Cite this