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 \(\delta^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 \(\delta^c(G)\geq n/2\), then for every two vertices \(u, v\) there is a properly-colored \(u,v\)-path in \(G\). We show that for sufficiently large graphs \(G\) the same bound for \(\delta^c(G)\) implies that any two vertices are connected by a rainbow path.

This is joint work with Andrzej Czygrinow.