کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646746 1342312 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Existence of rainbow matchings in strongly edge-colored graphs
ترجمه فارسی عنوان
وجود هماهنگی های رنگین کمان در نمودارهای لبه بشدت رنگی
کلمات کلیدی
تطابق رنگین کمان؛ نمودارهای لبه بشدت رنگی؛ مربع لاتین
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The famous Ryser Conjecture states that there is a transversal of size nn in a latin square of odd order nn, which is equivalent to finding a rainbow matching of size nn in a properly edge-colored Kn,nKn,n when nn is odd. Let δδ denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function f(δ)f(δ) (f(δ)≥2δ+1f(δ)≥2δ+1) such that for each properly edge-colored graph of order f(δ)f(δ), there exists a rainbow matching of size δδ. The best bound so far is f(δ)≤3.5δ+2f(δ)≤3.5δ+2 due to Lo. Babu et al. considered this problem in strongly edge-colored graphs in which each path of length 3 is rainbow. They proved that if GG is a strongly edge-colored graph of order at least 2⌊3δ4⌋, then GG has a rainbow matching of size ⌊3δ4⌋. They proposed an interesting question: Is there a constant cc greater than 34 such that every strongly edge-colored graph GG has a rainbow matching of size at least cδcδ if |V(G)|≥2⌊cδ⌋|V(G)|≥2⌊cδ⌋? Clearly, c≤1c≤1. We prove that if GG is a strongly edge-colored graph with minimum degree δδ and order at least 2δ+22δ+2, then GG has a rainbow matching of size δδ.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 10, 6 October 2016, Pages 2457–2460
نویسندگان
, , ,