2007/11/19 by Xueliang Li, Li, Xueliang, Zhixia Xu +1
Computer Science · Mathematics · #05C15 #05C35 #05C55 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C35 #msc:05C55 #msc:05C70
paper · pdf · doi:10.48550/arxiv.0711.2846
9 pages
arxiv created 2007/11/19 · openalex publication_date 2007/11/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 mK2 a matching of size m and Bn,k a k-regular bipartite graph with bipartition (X,Y) such that |X|=|Y|=n and k≤ n. In this paper we give an upper and lower bound for rb(Bn,k,mK2), and show that for given k and m, if n is large enough, rb(Bn,k,mK2) can reach the lower bound. We also determine the rainbow number of matchings in paths and cycles.