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

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