Georgia Institute of Technology College of Sciences

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$.
In this paper, we show that 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.

This is to note that the graph theory seminar for Friday the 4th has been CANCELLED. This is due to the cancellation of the AMS sectional meeting due to Hurricane Helene. I apologize for any inconvenience. We intend to reschedule the talk for next semester.