Packing two forests into a bipartite graph

✍ Scribed by Wang, Hong

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 292 KB
• Volume: 23
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199610)23:2<209::aid-jgt12>3.0.co;2-b

✦ 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 /XI = 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 note, we prove that any two compatible trees of order n can be packed into a complete bipartite graph of order at most n + 1. We also provide a family of infinitely many pairs of compatible trees which cannot be packed into a complete bipartite graph of the same order. A theorem about packing two forests into a complete bipartite graph is derived from this result.