Bipartite Rainbow Numbers of Matchings
| dc.creator | Li, Xueliang | |
| dc.creator | Tu, Jianhua | |
| dc.creator | Jin, Zemin | |
| dc.date | 2006-10-30 | |
| dc.date.accessioned | 2026-07-07T07:29:36Z | |
| dc.date.available | 2026-07-07T07:29:36Z | |
| dc.description | 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ős, Simonovits and Só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$. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/math/0610910 | |
| dc.identifier | http://arxiv.org/abs/math/0610910 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/118174 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C55; 05C70 | |
| dc.title | Bipartite Rainbow Numbers of Matchings | |
| dc.type | text |