Mathematics – Combinatorics
Scientific paper
2006-11-16
Mathematics
Combinatorics
20 pages
Scientific paper
For a given graph $H$ and $n\geq 1$, let $f(n,H)$ denote the maximum number $c$ for which there is a way to color the edges of the complete graph $K_n$ with $c$ colors such that every subgraph $H$ of $K_n$ has at least two edges of the same color. Equivalently, any edge-coloring of $K_n$ with at least $rb(n,H)=f(n,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(n,H)$ is called the {\it rainbow number of $H$}. Erd\H{o}s, Simonovits and S\'{o}s showed that $rb(n,K_3)=n$. In 2004, Schiermeyer used some counting technique and determined the rainbow numbers $rb(n,kK_2)$ for $k\geq 2$ and $n\geq 3k+3$. It is easy to see that $n$ must be at least $2k$. So, for $2k \leq n<3k+3$, the rainbow numbers remain not determined. In this paper we will use the Gallai-Edmonds structure theorem for matchings to determine the exact values for rainbow numbers $rb(n,kK_2)$ for all $k\geq 2$ and $n\geq 2k$, giving a complete solution for the rainbow numbers of matchings.
Chen He
Li Xueliang
Tu Jianhua
No associations
LandOfFree
Complete Solution for the 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 Complete Solution for the Rainbow Numbers of Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complete Solution for the Rainbow Numbers of Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-623158