کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903474 1632568 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Topological methods for the existence of a rainbow matching
ترجمه فارسی عنوان
روش های توپولوژیکی برای تطبیق رنگین کمان
کلمات کلیدی
تطبیق جزئی رنگین کمان، تطبیق رنگین کمان کامل، گراف دو طرفه، خط مشی ریسر برادلی، حدس استین،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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 63, December 2017, Pages 479-484
نویسندگان
, , , ,