Rainbow number of matchings in regular bipartite graphs
| dc.creator | Li, Xueliang | |
| dc.creator | Xu, Zhixia | |
| dc.date | 2007-11-19 | |
| dc.date.accessioned | 2026-07-07T08:43:41Z | |
| dc.date.available | 2026-07-07T08:43:41Z | |
| dc.description | 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. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/0711.2846 | |
| dc.identifier | http://arxiv.org/abs/0711.2846 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142401 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15; 05C35; 05C55; 05C70 | |
| dc.title | Rainbow number of matchings in regular bipartite graphs | |
| dc.type | text |