Exact rainbow numbers for 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 its edges have different colors. Denote by $M_t$ a matching of size $t$ and ${\mathcal{T}}_n$ the class of all plane triangulations of order $n$, respectively. Jendrol', Schiermeyer and Tu initiated to investigate the rainbow numbers for matchings in plane triangulations, and proved some bounds for the value of $rb({\mathcal{T}}_n,M_t)$. Chen, Lan and Song proved that $2n+3t-14\le rb({\mathcal{T}}_n,M_t)\le 2n+4t-13$ for all $n\ge 3t-6$ and $t\ge 6$. In this paper, we determine the exact values of $rb({\mathcal{T}}_n,M_t)$ for large $n$, namely, $rb({\mathcal{T}}_n,M_t)=2n+3t-14$ for all $n\ge 9t+3$ and $t\ge 7$.

10 pages

References in corpus (1)

• Planar anti-Ramsey numbers for paths and cycles