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. We also show sufficient conditions on $\delta^c(G)$ for the existence of a rainbow cycle of length $2k$ in sufficiently large bipartite graphs $G$, which are tight in many cases. This is joint work with Andrzej Czygrinow.
Welcome Eero Räty, Xiaofan Yuan, and Xin Wei, new members of IBS ECOPRO
The IBS Discrete Mathematics Group welcomes Dr. Eero Räty, Dr. Xiaofan Yuan, and Dr. Xin Wei, new research fellows at the IBS Extremal Combinatorics and Probability Group, starting January 1, 2026.
Dr. Eero Räty received his Ph.D. from the University of Cambridge under the supervision of Prof. Imre Leader. Until recently, he was a postdoctoral researcher at Umeå University, Sweden. He is interested in extremal and probabilistic combinatorics.
Dr. Xiaofan Yuan received her Ph.D. from the Georgia Institute of Technology under the supervision of Prof. Xingxing Yu. She is interested in graph theory and extremal combinatorics. Until recently, she was a postdoctoral researcher at Arizona State University.
Dr. Xin Wei received his Ph.D. from the University of Science and Technology of China under the supervision of Prof. Xiande Zhang. His research interests include combinatorics, coding theory, and graph theory and their interactions.