کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649790 | 1342465 | 2009 | 4 صفحه PDF | دانلود رایگان |
Given two graphs GG and HH, let f(G,H)f(G,H) denote the maximum number cc for which there is a way to color the edges of GG with cc colors such that every subgraph HH of GG has at least two edges of the same color. Equivalently, any edge-coloring of GG with at least rb(G,H)=f(G,H)+1rb(G,H)=f(G,H)+1 colors contains a rainbow copy of HH, 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)rb(G,H) is called the rainbow number of HHwith respect to GG, and simply called the bipartite rainbow number of HH if GG is the complete bipartite graph Km,nKm,n. Erdős, Simonovits and Sós showed that rb(Kn,K3)=nrb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk)rb(Kn,Kk) for all n≥k≥4n≥k≥4, and the rainbow numbers rb(Kn,kK2)rb(Kn,kK2) for all k≥2k≥2 and n≥3k+3n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2)rb(Km,n,kK2) for all k≥1k≥1.
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2575–2578