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 {\displaystyle G} is the minimum number of colors needed to rainbow-connect G {\displaystyle G} , and is denoted by rc ( G ) {\displaystyle {\text{rc}}(G)} . Similarly, the strong rainbow connection number of a graph G {\displaystyle G} is the minimum number of colors needed to strongly rainbow-connect G {\displaystyle G} , and is denoted by src ( G ) {\displaystyle {\text{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 {\displaystyle G} , we need at least diam ( G ) {\displaystyle {\text{diam}}(G)} colors, where diam ( G ) {\displaystyle {\text{diam}}(G)} is the diameter of G {\displaystyle G} (i.e. the length of the longest shortest path). On the other hand, we can never use more than m {\displaystyle m} colors, where m {\displaystyle m} denotes the number of edges in G {\displaystyle G} . Finally, because each strongly rainbow-connected graph is rainbow-connected, we have that diam ( G ) ≤ rc ( G ) ≤ src ( G ) ≤ m {\displaystyle {\text{diam}}(G)\leq {\text{rc}}(G)\leq {\text{src}}(G)\leq m} . The following are the extremal cases:
rc ( G ) = src ( G ) = 1 {\displaystyle {\text{rc}}(G)={\text{src}}(G)=1} if and only if G {\displaystyle G} is a complete graph.
rc ( G ) = src ( G ) = m {\displaystyle {\text{rc}}(G)={\text{src}}(G)=m} if and only if G {\displaystyle G} is a tree. The above shows that in terms of the number of vertices, the upper bound rc ( G ) ≤ n − 1 {\displaystyle {\text{rc}}(G)\leq n-1} is the best possible in general. In fact, a rainbow coloring using n − 1 {\displaystyle n-1} colors can be constructed by coloring the edges of a spanning tree of G {\displaystyle G} in distinct colors. The remaining uncolored edges are colored arbitrarily, without introducing new colors. When G {\displaystyle G} is 2-connected, we have that rc ( G ) ≤ ⌈ n / 2 ⌉ {\displaystyle {\text{rc}}(G)\leq \lceil n/2\rceil } . Moreover, this is tight as witnessed by e.g. odd cycles. For every bridgeless graph G {\displaystyle G} with radius r {\displaystyle r} , r c ( G ) ≤ r ( r + 2 ) {\displaystyle rc(G)\leq r(r+2)} . The very strong rainbow connection number ( v s r c ( G ) {\displaystyle vsrc(G)} ) is the minimum number of colors required to color the edges of a graph G {\displaystyle G} such that every shortest path between any two vertices is a rainbow path. While approximating v s r c ( G ) {\displaystyle vsrc(G)} for a general graph G {\displaystyle G} is an NP-hard problem, it can be solved in polynomial time for certain graph classes, such as cactus graphs.
Exact rainbow or strong rainbow connection numbers The rainbow or the strong rainbow connection number has been determined for some structured graph classes:
rc ( C n ) = src ( C n ) = ⌈ n / 2 ⌉ {\displaystyle {\text{rc}}(C_{n})={\text{src}}(C_{n})=\lceil n/2\rceil } , for each integer n ≥ 4 {\displaystyle n\geq 4} , where C n {\displaystyle C_{n}} is the cycle graph.
… excerpt ends here. Continue reading the full article.
