Packing two bipartite graphs into a complete bipartite graph

✍ Scribed by Wang, Hong

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 131 KB
• Volume: 26
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199710)26:2<95::aid-jgt4>3.0.co;2-a

✦ Synopsis

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, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove that any two compatible C 4 -free bipartite graphs of order n together with at most 2n -2 edges can be packed into a complete bipartite graph of order at most n + 1, unless one is the union of vertex-disjoint cycles and the other is the union of two vertex-disjoint stars. This theorem fails for non-C 4 -free bipartite graphs. We will provide a family of non-C 4 -free bipartite graphs to serve as examples. As in Wang and Sauer (1993) (H. Wang and N. Sauer, Packing three copies of a tree into a complete graph, Eur. J. Combinatorics 14 (1993), 137-142) for each of infinitely many n, there is a pair of compatible forests of order n which cannot be packed into a complete bipartite graph of order n.