Premium
Packing two forests into a bipartite graph
Author(s) -
Wang Hong
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199610)23:2<209::aid-jgt12>3.0.co;2-b
Subject(s) - combinatorics , bipartite graph , mathematics , edge transitive graph , complete bipartite graph , robertson–seymour theorem , graph , discrete mathematics , order (exchange) , graph power , line graph , 1 planar graph , finance , economics
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 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. © 1996 John Wiley & Sons, Inc.