کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902858 1632394 2018 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on rainbow matchings in strongly edge-colored graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A note on rainbow matchings in strongly edge-colored graphs
چکیده انگلیسی
The Ryser Conjecture which states that there is a transversal of size n in a Latin square of odd order n is equivalent to finding a rainbow matching of size n in a properly edge-colored Kn,n using n colors when n is odd. Let δ be the minimum degree of a graph. Wang proposed a more general question to find a function f(δ) such that every properly edge-colored graph of order f(δ) contains a rainbow matching of size δ, which currently has the best bound of f(δ)≤3.5δ+2 by Lo. Babu, Chandran and Vaidyanathan investigated Wang's question under a stronger color condition. A strongly edge-colored graph is a properly edge-colored graph in which every monochromatic subgraph is an induced matching. Wang, Yan and Yu proved that every strongly edge-colored graph of order at least 2δ+2 has a rainbow matching of size δ. In this note, we extend this result to graphs of order at least 2δ+1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 10, October 2018, Pages 2762-2767
نویسندگان
, , ,