Complete bipartite graphs without small rainbow stars

Abstract

The $k$-edge-colored bipartite Gallai-Ramsey number ${\mathrm{bgr}}_k(G:H)$ is defined as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every edge-coloring (using all $k$ colors) of complete bipartite graph $K_{N,N}$ contains a rainbow copy of $G$ or a monochromatic copy of $H$. In this paper, we first study the structural theorem on the complete bipartite graph $K_{n,n}$ with no rainbow copy of $K_{1,3}$. Next, we utilize the results to prove the exact values of ${\mathrm{bgr}}_k(P_4:H)$, ${\mathrm{bgr}}_k(P_5:H)$, ${\mathrm{bgr}}_k(K_{1,3}:H)$, where $H$ is a various union of cycles and paths and stars.

13 pages