Rainbow number of matchings in regular bipartite graphs

Abstract

Given a graph $G$ and a subgraph $H$ of $G$, let $rb(G,H)$ be the minimum number $r$ for which any edge-coloring of $G$ with $r$ colors has a rainbow subgraph $H$. The number $rb(G,H)$ is called the rainbow number of $H$ with respect to $G$. Denote $m{K}_2$ a matching of size $m$ and $B_{n,k}$ a $k$-regular bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|=n$ and $k\le n$. In this paper we give an upper and lower bound for $rb(B_{n,k},m{K}_2)$, and show that for given $k$ and $m$, if $n$ is large enough, $rb(B_{n,k},m{K}_2)$ can reach the lower bound. We also determine the rainbow number of matchings in paths and cycles.

9 pages