A note on rainbow matchings in strongly edge-colored graphs
| Autor: | Yangyang Cheng, Ta Sheng Tan, Guanghui Wang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Conjecture Colored graph 020206 networking & telecommunications Rainbow 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Monochromatic color Mathematics |
| Zdroj: | Discrete Mathematics. 341:2762-2767 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2018.06.019 |
| Popis: | 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 , 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 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect