Article ID Journal Published Year Pages File Type
4649790 Discrete Mathematics 2009 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,