Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Altgeld 147
- Date
- Apr 24, 2025 1:00 pm
- Speaker
- Xiaofan Yuan (ASU)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 55
Speaker: Xiaofan Yuan (Arizona State University)
Title: Tight minimum colored degree condition for rainbow connectivity
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.