Complete Solution for the Rainbow Numbers of Matchings

Simple item page
dc.creatorChen, He
dc.creatorLi, Xueliang
dc.creatorTu, Jianhua
dc.date2006-11-16
dc.date.accessioned2026-07-07T07:33:00Z
dc.date.available2026-07-07T07:33:00Z
dc.descriptionFor 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ős, Simonovits and Só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.
dc.description20 pages
dc.identifierhttps://arxiv.org/abs/math/0611490
dc.identifierhttp://arxiv.org/abs/math/0611490
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/119311
dc.subjectCombinatorics
dc.subject05C35; 05C55; 05C70
dc.titleComplete Solution for the Rainbow Numbers of Matchings
dc.typetext

Files

Collections

arXiv