Existences of rainbow matchings and rainbow matching covers

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

Let G be an edge-coloured graph. A rainbow subgraph in G is a subgraph such that its edges have distinct colours. The minimum colour degree δc(G) of G is the smallest number of distinct colours on the edges incident with a vertex of G. We show that every edge-coloured graph G on n≥7k/2+2 vertices with δc(G)≥k contains a rainbow matching of size at least k, which improves the previous result for k≥10.  
Let Δmon(G) be the maximum number of edges of the same colour incident with a vertex of G. We also prove that if t≥11 and Δmon(G)≤t, then G can be edge-decomposed into at most ⌊tn/2⌋ rainbow matchings. This result is sharp and improves a result of LeSaulnier and West.

Details

Original languageEnglish
Pages (from-to)2119-2124
Number of pages6
JournalDiscrete Mathematics
Volume338
Early online date9 Jun 2015
Publication statusPublished - 6 Nov 2015

Keywords

  • Edge coloring, Rainbow, Matching