2021/07/12 by Peter Bradshaw, Bradshaw, Peter, Bojan Mohar +1
Computer Science · Mathematics · Physics and Astronomy · #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2107.05670
openalex publication_date 2021/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a family \mathcal G of graphs on a common vertex set X, we say that \mathcal G is rainbow connected if for every vertex pair u,v ∈ X, there exists a path from u to v that uses at most one edge from each graph in \mathcal G. We consider the case that \mathcal G contains s graphs, each sampled randomly from G(n,p), with n = |X| and p = (c log n)/(sn), where c > 1 is a constant. We show that when s is sufficiently large, \mathcal G is a.a.s. rainbow connected, and when s is sufficiently small, \mathcal G is a.a.s. not rainbow connected. We also calculate a threshold of s for the rainbow connectivity of \mathcal G, and we show that this threshold is concentrated on at most three values, which are larger than the diameter of the union of \mathcal G by about (log n)/((log log n)2). The same results also hold in a more traditional random rainbow setting, where we take a random graph G∈ G(n,p) with p=(c log n)/(n) (c>1) and color each edge of G with a color chosen uniformly at random from the set [s] of s colors.