- 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→P, where P is a set of colors. Let δc(G)=minv∈V{dc(v)} where dc(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 δc(G)≥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 δc(G) implies that any two vertices are connected by a rainbow path. This is joint work with Andrzej Czygrinow.