Tight minimum colored degree condition for rainbow connectivity

Abstract

Let $G=(V,E)$ be a graph on $n$ vertices, and let $c:E\to P$, where $P$ is a set of colors. Let $\hat{I}{´}^c(G)={\min }_{v\in V}\{d^c(v)\}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$. In 2011, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\hat{I}{´}^c(G)\ge n/2$, then for every two vertices $u,v$ there is a properly-colored $u,v$-path in $G$. In this paper, we show that the same bound for $\hat{I}{´}^c(G)$ implies that any two vertices are connected by a rainbow path.