Rainbow matchings in strongly edge-colored graphs

• Published in: Discrete mathematics 2015-07, Vol.338 (7), p.1191-1196
• Main Authors: Babu, Jasine, Chandran, L. Sunil, Vaidyanathan, Krishna
• Format: Article
• Language: English
• Subjects: Edge-colored graphs; Rainbow matching; Strong edge-coloring
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2014.12.019

A rainbow matching of an edge-colored graph G 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 G in terms of its minimum degree δ(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f(δ(G)) vertices is guaranteed to contain a rainbow matching of size δ(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k)=4k−4, for k≥4 and f(k)=4k−3, for k≤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)−4 vertices. Strong edge-coloring of a graph G 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 G in terms of δ(G). We show that for a strongly edge-colored graph G, if |V(G)|≥2⌊3δ(G)4⌋, then G has a rainbow matching of size ⌊3δ(G)4⌋, and if |V(G)|