Existences of rainbow matchings and rainbow matching covers

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\geq 7k/2+2$ vertices with $δ^c(G) \geq k$ contains a rainbow matching of size at least $k$, which improves the previous result for $k \ge 10$. Let $Δ_{\text{mon}}(G)$ be the maximum number of edges of the same colour incident with a vertex of $G$. We also prove that if $t \ge 11$ and $Δ_{\text{mon}}(G) \le t$, then $G$ can be edge-decomposed into at most $\lfloor tn/2 \rfloor$ rainbow matchings. This result is sharp and improves a result of LeSaulnier and West.

No reviews yet.

No comments yet.