Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902858 | Discrete Mathematics | 2018 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yangyang Cheng, Ta Sheng Tan, Guanghui Wang,