Rainbow coloring
# Rainbow coloring

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.

