کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647268 1632411 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rainbow numbers for matchings in plane triangulations
ترجمه فارسی عنوان
شماره رنگین کمان برای مسابقات در سه گانه هواپیما
کلمات کلیدی
گراف لبه رنگ زیرگرافی رنگین کمان، شماره رنگین کمان، تطابق، سه گانه هواپیما
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 331, 28 September 2014, Pages 158–164
نویسندگان
, , ,