A Note on Large Rainbow Matchings in Edge-coloured Graphs |
| |
| Authors: | Allan Lo Ta Sheng Tan |
| |
| Institution: | 1. School of Mathematics, University of Birmingham, Birmingham, B15 2TT, UK
2. Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, UK
|
| |
| Abstract: | A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided ${n\geq \frac{17}{4}k^2}$ . In this paper, we show that n ≥ 4k ? 4 is sufficient for k ≥ 4. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
