Originator: Yair Caro et al (presented by D. West - REGS 2008)
Definitions: Given an edge-coloring of a graph, a subgraph is a rainbow subgraph if its edges have distinct colors. An edge-coloring of a graph is rainbow-connected if every two vertices are connected via a rainbow path. The rainbow connectedness of a graph G, written rc(G), is the minimum number of colors in a rainbow-connected edge-coloring. These concepts were introduced by Chartrand et al in two papers that computed rainbow connectedness in various special classes, under the name rainbow connectivity.
Background: Note that always rc(G)≥diam G. Thus the complete graph is the only n-vertex graph with rainbow connectedness 1. In general, we seek upper bounds on rc(G) in terms of the number of vertices (n) and perhaps other parameters.
Conjecture 1 [CLRTY]: If δ(G)≥3, then rc(G)<3n/4.
Comments: Caro et al [CLRTY] proved that rc(G)<5n/6. The conjectured bound would be essentially sharp; they presented infinite families of graphs with minimum degree 3 and rainbow connectedness (3n-10)/4. When δ(G)=k, they showed that rc(G)≤(1+o(1))cn, where c=(lnk)/k.
Question 2: What is the edge-probability threshold for rainbow connectedness 2 in the random graph?
Question 3 (Kündgen-West): Is there a function f such that always rc(G)≤diam G? In particular, is the rainbow connectedness of graphs with diameter 2 bounded?
Comments: Possibly the rainbow connectedness of graphs with diameter 2 is at most 5. Chartrand et al [CJMZ1] determined the value for all complete multipartite graphs; it is 2 or 3. The value is 3 for the Petersen graph and at most 6 for incidence graphs of projective planes. If G consists of edge-disjoint cycles with a common vertex, then rc(G) is at most twice the diameter.
References:
[CLRTY]
Y. Caro, A. Lev, Y. Roditty, Zs. Tuza, and R. Yuster,
On rainbow connection. Electr. J. Combin. 15 (2008), Paper R57, 13 pages.
[CJMZ1]
Chartrand, Gary; Johns, Garry L.; McKeon, Kathleen A.; Zhang, Ping; Rainbow
connection in graphs. Math. Bohem. 133 (2008), no. 1, 85--98.
[CJMZ2]
Chartrand, Gary; Johns, Garry L.; McKeon, Kathleen A.; Zhang, Ping; The rainbow
connectivity of a graph. preprint