Rainbow number of matchings in regular bipartite graphs

Details Rainbow number of matchings in regular bipartite graphs Rainbow number of matchings in regular bipartite graphs

2007-11-19

arxiv.org/abs/0711.2846v1

Mathematics

Combinatorics

9 pages

Scientific paper

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 $mK_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\leq n$. In this paper we give an upper and lower bound for $rb(B_{n,k},mK_2)$, and show that for given $k$ and $m$, if $n$ is large enough, $rb(B_{n,k},mK_2)$ can reach the lower bound. We also determine the rainbow number of matchings in paths and cycles.

Affiliated with

Also associated with

No associations

Rating

Rainbow number of matchings in regular bipartite graphs 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 Rainbow number of matchings in regular bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow number of matchings in regular bipartite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115568