In graph theory, a path in an edge-colored graph is said to be rainbow if no color repeats on it. A graph is said to be rainbow-connected (or rainbow colored) if there is a rainbow path between each pair of its vertices. If there is a rainbow shortest path between each pair of vertices, the graph is said to be strongly rainbow-connected (or strongly rainbow colored).
Definitions and bounds
The rainbow connection number of a graph G is the minimum number of colors needed to rainbow-connect G , and is denoted by rc ( G ) . Similarly, the strong rainbow connection number of a graph G is the minimum number of colors needed to strongly rainbow-connect G , and is denoted by src ( G ) . Clearly, each strong rainbow coloring is also a rainbow coloring, while the converse is not true in general.
It is easy to observe that to rainbow-connect any connected graph G , we need at least diam ( G ) colors, where diam ( G ) is the diameter of G (i.e. the length of the longest shortest path). On the other hand, we can never use more than m colors, where m denotes the number of edges in G . Finally, because each strongly rainbow-connected graph is rainbow-connected, we have that diam ( G ) ≤ rc ( G ) ≤ src ( G ) ≤ m .
The following are the extremal cases:
rc ( G ) = src ( G ) = 1 if and only if G is a complete graph. rc ( G ) = src ( G ) = m if and only if G is a tree.The above shows that in terms of the number of vertices, the upper bound rc ( G ) ≤ n − 1 is the best possible in general. In fact, a rainbow coloring using n − 1 colors can be constructed by coloring the edges of a spanning tree of G in distinct colors. The remaining uncolored edges are colored arbitrarily, without introducing new colors. When G is 2-connected, we have that rc ( G ) ≤ ⌈ n / 2 ⌉ . Moreover, this is tight as witnessed by e.g. odd cycles.
The rainbow or the strong rainbow connection number has been determined for some structured graph classes:
rc ( C n ) = src ( C n ) = ⌈ n / 2 ⌉ , for each integer n ≥ 4 , where C n is the cycle graph. rc ( W n ) = 3 , for each integer n ≥ 7 , and src ( W n ) = ⌈ n / 3 ⌉ , for n ≥ 3 , where W n is the wheel graph.The problem of deciding whether rc ( G ) = 2 for a given graph G is NP-complete. Because rc ( G ) = 2 if and only if src ( G ) = 2 , it follows that deciding if src ( G ) = 2 is NP-complete for a given graph G .
Variants and generalizations
Krivelevich and Yuster generalized the concept of rainbow connection to the vertex version. The rainbow vertex-connection number of a graph G is the minimum number of colors needed to color G such that for each pair of vertices, there is a path connecting them whose internal vertices are assigned distinct colors, and is denoted by rvc ( G ) .
Chartrand, Okamoto and Zhang generalized the rainbow connection number as follows. Let G be an edge-colored nontrivial connected graph of order n . A tree T is a rainbow tree if no two edges of T are assigned the same color. Let k be a fixed integer with 2 ≤ k ≤ n . An edge coloring of G is called a k -rainbow coloring if for every set S of k vertices of G , there is a rainbow tree in G containing the vertices of S . The k -rainbow index rx k ( G ) of G is the minimum number of colors needed in a k -rainbow coloring of G . A k -rainbow coloring using rx k ( G ) colors is called a minimum k -rainbow coloring. Thus rx 2 ( G ) is the rainbow connection number of G .
