Bipartite Rainbow Ramsey Numbers
by
Linda Eroh
University of Wisconsin Oshkosh
Coauthors: Ortrud Oellermann (University of Winnipeg)

We define the bipartite rainbow ramsey number BRR(G₁, G₂) of two bipartite graphs G₁ and G₂ to be the smallest integer N such that any coloring of the edges of the complete bipartite graph K_{N, N} with any number of colors must contain either a subgraph isomorphic to G₁ with every edge the same color or a subgraph isomorphic to G₂ with every edge a different color. This number exists if and only if one of the two graphs is a star or union of stars. For any integers n and m with 3 <= m <= n+2 and n >= 3, we show that BRR(K_{1, n}, mK₂)=(n-1)(m-1)+1. For n = 2, this problem is related to an unsolved conjecture in design theory, since BRR(K_{1, 2}, mK₂)=m if and only if every m by m latin square contains a transversal.

Date received: April 16, 2001