Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T18:00:39.941Z Has data issue: false hasContentIssue false

On Two Conjectures on Packing of Graphs

Published online by Cambridge University Press:  11 October 2005

BÉLA BOLLOBÁS
Affiliation:
University of Memphis, Memphis, TN 38152, USA and Trinity College, Cambridge CB2 1TQ, UK (e-mail: bollobas@msci.memphis.edu)
ALEXANDR KOSTOCHKA
Affiliation:
University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk 630090, Russia (e-mail: kostochk@math.uiuc.edu)
KITTIKORN NAKPRASIT
Affiliation:
University of Illinois, Urbana, IL 61801, USA (e-mail: nakprasi@math.uiuc.edu)
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.

In 1978, Bollobás and Eldridge [5] made the following two conjectures.

  1. (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.

  2. (C2) For all $0<\alpha<1/2$ and $0<c<\sqrt{1/8}$, there exists an $n_0=n_0(\alpha,c)$ such that, if $G_1$ and $G_2$ are graphs of order $n>n_0$ satisfying $e(G_1)\leq \alpha n$ and $e(G_2)\leq c\sqrt{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<1$. We also give sufficient conditions for simultaneous packings of about $\sqrt{n}/4$ sparse graphs.

Information

Type
Paper
Copyright
2005 Cambridge University Press