کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653679 | 1632781 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Large matchings in bipartite graphs have a rainbow matching
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let g(n)g(n) be the least number such that every collection of nn matchings, each of size at least g(n)g(n), in a bipartite graph, has a full rainbow matching. Aharoni and Berger (2009) conjectured that g(n)=n+1g(n)=n+1 for every n>1n>1. This generalizes famous conjectures of Ryser, Brualdi and Stein. Recently, Aharoni et al. proved that g(n)≤⌊74n⌋. We prove that g(n)≤⌊53n⌋.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 38, May 2014, Pages 97–101
Journal: European Journal of Combinatorics - Volume 38, May 2014, Pages 97–101
نویسندگان
Daniel Kotlar, Ran Ziv,