کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423637 1632577 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On rainbow matchings in bipartite graphs
ترجمه فارسی عنوان
در بازیابی رنگین کمان در گراف دو طرفه
کلمات کلیدی
تطبیق جزئی رنگین کمان، تطبیق رنگین کمان کامل، گراف دو طرفه، خط مشی ریسر برادلی، حدس استین،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We present recent results regarding rainbow matchings in bipartite graphs. Using topological methods we address a known conjecture of Stein and show that if Kn,n is partitioned into n sets of size n, then a partial rainbow matching of size 2n/3 exists. We generalize a result of Cameron and Wanless and show that for any n matchings of size n in a bipartite graph with 2n vertices there exists a full matching intersecting each matching at most twice. We show that any n matchings of size approximately 3n/2 have a rainbow matching of size n. Finally, we show the uniqueness of the extreme case for a theorem of Drisko and provide a generalization of Drisko's theorem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 33-38
نویسندگان
, , , ,