Projects per year
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.
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.
Original language | English |
---|---|
Pages (from-to) | 2119-2124 |
Number of pages | 6 |
Journal | Discrete Mathematics |
Volume | 338 |
Early online date | 9 Jun 2015 |
DOIs | |
Publication status | Published - 6 Nov 2015 |
Keywords
- Edge coloring
- Rainbow
- Matching
Fingerprint
Dive into the research topics of 'Existences of rainbow matchings and rainbow matching covers'. Together they form a unique fingerprint.Projects
- 1 Finished
-
FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs
European Commission, European Commission - Management Costs
1/12/10 → 30/11/15
Project: Research