PACKING 2 BIPARTITE GRAPHS INTO A COMPLETE BIPARTITE GRAPH

For two integers a and b, we say that a bipartite graph G admits an (a , b)-bipartition if G has a bipartition (X, Y) such that \X\ = a and \ Y\ = b. We say that two bipartite graphs G and H are compatible if, fo r some integers a and b, both G and H admit (a, b)-bipartitions. In th is paper, we prove that any two compatible C-4-free bipartite graphs o f order n together with at most 2n - 2 edges can be packed into a comp lete bipartite graph of order al most n + 1, unless one is the union o f vertex-disjoint cycles and the other is the union of two vertex-disj oint stars. This theorem fails for non-C-4-free bipartite graphs. We w ill provide a family of non-C-4-free bipartite graphs to serve as exam ples. As in Wang and Sauer (1993) (H. Wang and N. Sauer, Packing three copies of a tree into a complete graph, fur. J. Combinatorics 14 (199 3), 137-142) for each of infinitely many n, there is a pair of compati ble forests of order n which cannot be packed into a complete bipartit e graph of order n. (C) 1997 John Wiley & Sons, Inc.