On packing bipartite graphs

G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of , the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.the paper was written while the authors were graduate students at the University of Chicago and was completed while the first author was at M.I.T. The work of the first author was supported in part by the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. The work of the second author was supported in part by NSF grant CCR-8706518.