Article ID Journal Published Year Pages File Type
8902858 Discrete Mathematics 2018 6 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,