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

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
نویسندگان
, ,