pith. sign in

arxiv: 0711.2846 · v1 · submitted 2007-11-19 · 🧮 math.CO

Rainbow number of matchings in regular bipartite graphs

classification 🧮 math.CO
keywords numberrainbowbipartiteboundgivengraphlowermatchings
0
0 comments X
read the original 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 $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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.