کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647268 | 1632411 | 2014 | 7 صفحه 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. If GG is a complete graph KnKn, the numbers f(Kn,H)f(Kn,H) and rb(Kn,H)rb(Kn,H) are called anti-Ramsey numbers and rainbow numbers, respectively.In this paper we will study the existence of rainbow matchings in plane triangulations. Denote by kK2kK2 a matching of size kk and TnTn the class of all plane triangulations of order nn. The rainbow number rb(Tn,kK2)rb(Tn,kK2) is the minimum number of colors cc such that, if kK2⊆Tn∈TnkK2⊆Tn∈Tn, then any edge-coloring of TnTn with at least cc colors contains a rainbow copy of kK2kK2. We give lower and upper bounds on rb(Tn,kK2)rb(Tn,kK2) for all k≥3k≥3 and n≥2kn≥2k. Furthermore, we obtain the exact values of rb(Tn,kK2)rb(Tn,kK2) for 2≤k≤42≤k≤4 and n≥2kn≥2k.
Journal: Discrete Mathematics - Volume 331, 28 September 2014, Pages 158–164