Tight minimum colored degree condition for rainbow connectivity

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.eduhttps://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:EP, where P is a set of colors. Let δc(G)=minvV{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.