Mathematics – Combinatorics
Scientific paper
2006-10-30
Mathematics
Combinatorics
8 pages
Scientific paper
Given two graphs $G$ and $H$, let $f(G,H)$ denote the maximum number $c$ for which there is a way to color the edges of $G$ with $c$ colors such that every subgraph $H$ of $G$ has at least two edges of the same color. Equivalently, any edge-coloring of $G$ with at least $rb(G,H)=f(G,H)+1$ colors contains a rainbow copy of $H$, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number $rb(G,H)$ is called the {\it rainbow number of $H$ with respect to $G$}, and simply called the {\it bipartite rainbow number of $H$} if $G$ is the complete bipartite graph $K_{m,n}$. Erd\H{o}s, Simonovits and S\'{o}s showed that $rb(K_n,K_3)=n$. In 2004, Schiermeyer determined the rainbow numbers $rb(K_n,K_k)$ for all $n\geq k\geq 4$, and the rainbow numbers $rb(K_n,kK_2)$ for all $k\geq 2$ and $n\geq 3k+3$. In this paper we will determine the rainbow numbers $rb(K_{m,n},kK_2)$ for all $k\geq 1$.
Jin Zemin
Li Xueliang
Tu Jianhua
No associations
LandOfFree
Bipartite Rainbow Numbers of Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bipartite Rainbow Numbers of Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bipartite Rainbow Numbers of Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-230958