- Series
- Graph Theory Seminar
- Time
- Tuesday, March 11, 2025 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Xiaofan Yuan – Arizona State University – xyuan52@asu.edu – https://search.asu.edu/profile/4226552
- Organizer
- Rose McCarty and Evelyne Smith-Roberge
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.