Improved bounds for rainbow numbers of matchings in plane triangulations

Abstract

Given two graphs $G$ and $H$, the {\it rainbow number} $rb(G,H)$ for $H$ with respect to $G$ is defined as the minimum number $k$ such that any $k$-edge-coloring of $G$ contains a rainbow $H$, i.e., a copy of $H$, all of whose edges have different colors. Denote by $k{K}_2$ a matching of size $k$ and ${\mathcal{T}}_n$ the class of all plane triangulations of order $n$, respectively. In [S. Jendrol${}^{\prime }$, I. Schiermeyer and J. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331(2014), 158--164], the authors determined the exact values of $rb({\mathcal{T}}_n,k{K}_2)$ for $2\le k\le 4$ and proved that $2n+2k-9\le rb({\mathcal{T}}_n,k{K}_2)\le 2n+2k-7+2\left(\genfrac{}{}{0ex}{}{2k-2}{3}\right)$ for $k\ge 5$. In this paper, we improve the upper bounds and prove that $rb({\mathcal{T}}_n,k{K}_2)\le 2n+6k-16$ for $n\ge 2k$ and $k\ge 5$. Especially, we show that $rb({\mathcal{T}}_n,5K_2)=2n+1$ for $n\ge 11$.

8 pages, to appear in Discrete Mathematics