A note on rainbow matchings in strongly edge-colored graphs

作者：Cheng, Yangyang; Tan, Ta Sheng; Wang, Guanghui^*

来源：Discrete Mathematics, 2018, 341(10): 2762-2767.

DOI：10.1016/j.disc.2018.06.019

• Rainbow matching
• Strongly edge-colored graph
• Ryser Conjecture
• Latin square

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 K-n,K-n using n colors when n is odd. Let delta be the minimum degree of a graph. Wang proposed a more general question to find a function f (delta) such that every properly edge-colored graph of order f(delta) contains a rainbow matching of size delta, which currently has the best bound of f(delta) <= 3.5 delta + 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 delta + 2 has a rainbow matching of size delta. In this note, we extend this result to graphs of order at least 2 delta + 1.

• 出版日期2018-10
• 单位山东大学