# Rainbow coloring Rainbow coloring of a wheel graph, with three colors. Every two non-adjacent vertices can be connected by a rainbow path, either directly through the center vertex (bottom left) or by detouring around one triangle to avoid a repeated edge color (bottom right).

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 ${\text{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 ${\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$ , we need at least ${\text{diam}}(G)$  colors, where ${\text{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 ${\text{diam}}(G)\leq {\text{rc}}(G)\leq {\text{src}}(G)\leq m$ .

The following are the extremal cases:

• ${\text{rc}}(G)={\text{src}}(G)=1$  if and only if $G$  is a complete graph.
• ${\text{rc}}(G)={\text{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 ${\text{rc}}(G)\leq 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 ${\text{rc}}(G)\leq \lceil n/2\rceil$ . Moreover, this is tight as witnessed by e.g. odd cycles.

## Exact rainbow or strong rainbow connection numbers

The rainbow or the strong rainbow connection number has been determined for some structured graph classes:

• ${\text{rc}}(C_{n})={\text{src}}(C_{n})=\lceil n/2\rceil$ , for each integer $n\geq 4$ , where $C_{n}$  is the cycle graph.
• ${\text{rc}}(W_{n})=3$ , for each integer $n\geq 7$ , and ${\text{src}}(W_{n})=\lceil n/3\rceil$ , for $n\geq 3$ , where $W_{n}$  is the wheel graph.

## Complexity

The problem of deciding whether ${\text{rc}}(G)=2$  for a given graph $G$  is NP-complete. Because ${\text{rc}}(G)=2$  if and only if ${\text{src}}(G)=2$ , it follows that deciding if ${\text{src}}(G)=2$  is NP-complete for a given graph $G$ .

## Variants and generalizations

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\leq k\leq 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 ${\text{rx}}_{k}(G)$  of $G$  is the minimum number of colors needed in a $k$ -rainbow coloring of $G$ . A $k$ -rainbow coloring using ${\text{rx}}_{k}(G)$  colors is called a minimum $k$ -rainbow coloring. Thus ${\text{rx}}_{2}(G)$  is the rainbow connection number of $G$ .

Rainbow connection has also been studied in vertex-colored graphs. This concept was introduced by Krivelevich and Yuster. Here, the rainbow vertex-connection number of a graph $G$ , denoted by ${\text{rvc}}(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.