<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 2" %>
Packing Three Copies of a Tree into a Complete Bipartite Graph
Hong Wang
Department of Mathematics, The University of Idaho, Moscow, Idaho 83844, USA
hwang@uidaho.edu
Annals of Combinatorics 13 (2) pp.261-269 June, 2009
AMS Subject Classification: 05C70
Abstract:
For any tree $T$ of order $n$, there is a packing of three copies of $T$ into a complete bipartite graph of order at most $n+2$. This result is sharp in the sense that $n+2$ can not be reduced to $n+1$ in general.
Keywords: packing, bipartite packing, embedding

References:

1. B. Bollob´as, Extremal Graph Theory, Academic Press, London-New York, 1978.

2. J.-L. Fouquet and A.P. Wojda, Mutual placement of bipartite graphs, Discrete Math. 121 (1-3) (1993) 85-–92.

3. A.M. Hobbs, B.A. Bourgeois, and J. Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1) (1987) 27-–42.

4. H. Wang, Packing two forests into a bipartite graph, J. Graph Theory 23 (2) (1996) 209–- 213.

5. H. Wang and N. Sauer, The chromatic number of the two packings of a forest, In: The Mathematics of Paul Erd¨os, II, Algorithms Combin., Vol. 14, R.L. Graham and J. Nesetril, Eds., Springer, Berlin, (1997) pp. 99-–120.

6. M. Wo´zniak, Packing of graphs and permutations — a survey, Discrete Math. 276 (1-3) (2004) 379-–391.

7. H.P. Yap, Packing of graphs —a survey, Discrete Math. 72 (1-3) (1988) 395-–404.