首页 | 本学科首页   官方微博 | 高级检索  
     


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 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:Rainbow matching  Strongly edge-colored graph  Ryser Conjecture  Latin square
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号