Article ID Journal Published Year Pages File Type
4646746 Discrete Mathematics 2016 4 Pages PDF
Abstract

The famous Ryser Conjecture states that there is a transversal of size nn in a latin square of odd order nn, which is equivalent to finding a rainbow matching of size nn in a properly edge-colored Kn,nKn,n when nn is odd. Let δδ denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function f(δ)f(δ) (f(δ)≥2δ+1f(δ)≥2δ+1) such that for each properly edge-colored graph of order f(δ)f(δ), there exists a rainbow matching of size δδ. The best bound so far is f(δ)≤3.5δ+2f(δ)≤3.5δ+2 due to Lo. Babu et al. considered this problem in strongly edge-colored graphs in which each path of length 3 is rainbow. They proved that if GG is a strongly edge-colored graph of order at least 2⌊3δ4⌋, then GG has a rainbow matching of size ⌊3δ4⌋. They proposed an interesting question: Is there a constant cc greater than 34 such that every strongly edge-colored graph GG has a rainbow matching of size at least cδcδ if |V(G)|≥2⌊cδ⌋|V(G)|≥2⌊cδ⌋? Clearly, c≤1c≤1. We prove that if GG is a strongly edge-colored graph with minimum degree δδ and order at least 2δ+22δ+2, then GG has a rainbow matching of size δδ.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,