کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649790 1342465 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bipartite rainbow numbers of matchings
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bipartite rainbow numbers of matchings
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2575–2578
نویسندگان
, , ,