کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646911 | 1342318 | 2015 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Rainbow matchings in strongly edge-colored graphs Rainbow matchings in strongly edge-colored graphs](/preview/png/4646911.png)
A rainbow matching of an edge-colored graph GG is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph GG in terms of its minimum degree δ(G)δ(G). Wang (2011) asked whether there exists a function ff such that a properly edge-colored graph GG with at least f(δ(G))f(δ(G)) vertices is guaranteed to contain a rainbow matching of size δ(G)δ(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k)=4k−4f(k)=4k−4, for k≥4k≥4 and f(k)=4k−3f(k)=4k−3, for k≤3k≤3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4δ(G)−44δ(G)−4 vertices. Strong edge-coloring of a graph GG is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph GG in terms of δ(G)δ(G). We show that for a strongly edge-colored graph GG, if |V(G)|≥2⌊3δ(G)4⌋, then GG has a rainbow matching of size ⌊3δ(G)4⌋, and if |V(G)|<2⌊3δ(G)4⌋, then GG has a rainbow matching of size ⌊|V(G)|2⌋. In addition, we prove that if GG is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least δ(G)δ(G).
Journal: Discrete Mathematics - Volume 338, Issue 7, 6 July 2015, Pages 1191–1196