Bipartite rainbow numbers of matchings
Bipartite rainbow numbers of matchings
复制标题
DOI：
10.1016/j.disc.2008.05.011
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Xueliang Li;J. Tu;Zemin Jin
中科院分区：
文献类型：
--
作者：
Xueliang Li;J. Tu;Zemin Jin
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 rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph Km,n. Erdős, Simonovits and Sós showed that rb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk) for all n≥k≥4, and the rainbow numbers rb(Kn,kK2) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2) for all k≥1.
