An Anti-Ramsey Problem Concerning Complete Bipartite Graphs

Abstract

We consider quadruples of positive integers $(a,b,m,n)$ with $a\le b$ and $m\le n$ such that any proper edge-coloring of the complete bipartite graph $K_{m,n}$ contains a rainbow $K_{a,b}$ subgraph. We show that any such quadruple with $a\le m$ and $n>(a^2-a+1)(b-1)$ satisfies this property. We also show that the quadruple $(2,3,3,6)$ satisfies this property. We end with a conjecture.

8 pages, 0 figures, supported by National Science Foundation grant no. 1262930