A note on rainbow matchings in strongly edge-colored graphs |
| |
Authors: | Yangyang Cheng Ta Sheng Tan Guanghui Wang |
| |
Affiliation: | 1. School of Mathematics, Shandong University, Jinan, 250100, China;2. Institute of Mathematical Sciences, Faculty of Science, University of Malaya, 50603 Kuala Lumpur, Malaysia |
| |
Abstract: | The Ryser Conjecture which states that there is a transversal of size in a Latin square of odd order is equivalent to finding a rainbow matching of size in a properly edge-colored using colors when is odd. Let be the minimum degree of a graph. Wang proposed a more general question to find a function such that every properly edge-colored graph of order contains a rainbow matching of size , which currently has the best bound of 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 has a rainbow matching of size . In this note, we extend this result to graphs of order at least . |
| |
Keywords: | Rainbow matching Strongly edge-colored graph Ryser Conjecture Latin square |
本文献已被 ScienceDirect 等数据库收录! |
|