# 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).[1]

## Definitions and bounds

The rainbow connection number of a graph ${\displaystyle G}$ is the minimum number of colors needed to rainbow-connect ${\displaystyle G}$, and is denoted by ${\displaystyle {\text{rc}}(G)}$. Similarly, the strong rainbow connection number of a graph ${\displaystyle G}$ is the minimum number of colors needed to strongly rainbow-connect ${\displaystyle G}$, and is denoted by ${\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 ${\displaystyle G}$, we need at least ${\displaystyle {\text{diam}}(G)}$ colors, where ${\displaystyle {\text{diam}}(G)}$ is the diameter of ${\displaystyle G}$ (i.e. the length of the longest shortest path). On the other hand, we can never use more than ${\displaystyle m}$ colors, where ${\displaystyle m}$ denotes the number of edges in ${\displaystyle G}$. Finally, because each strongly rainbow-connected graph is rainbow-connected, we have that ${\displaystyle {\text{diam}}(G)\leq {\text{rc}}(G)\leq {\text{src}}(G)\leq m}$.

The following are the extremal cases:[1]

• ${\displaystyle {\text{rc}}(G)={\text{src}}(G)=1}$ if and only if ${\displaystyle G}$ is a complete graph.
• ${\displaystyle {\text{rc}}(G)={\text{src}}(G)=m}$ if and only if ${\displaystyle G}$ is a tree.

The above shows that in terms of the number of vertices, the upper bound ${\displaystyle {\text{rc}}(G)\leq n-1}$ is the best possible in general. In fact, a rainbow coloring using ${\displaystyle n-1}$ colors can be constructed by coloring the edges of a spanning tree of ${\displaystyle G}$ in distinct colors. The remaining uncolored edges are colored arbitrarily, without introducing new colors. When ${\displaystyle G}$ is 2-connected, we have that ${\displaystyle {\text{rc}}(G)\leq \lceil n/2\rceil }$.[2] 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:

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

## Complexity

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

## Variants and generalizations

Chartrand, Okamoto and Zhang[4] generalized the rainbow connection number as follows. Let ${\displaystyle G}$ be an edge-colored nontrivial connected graph of order ${\displaystyle n}$. A tree ${\displaystyle T}$ is a rainbow tree if no two edges of ${\displaystyle T}$ are assigned the same color. Let ${\displaystyle k}$ be a fixed integer with ${\displaystyle 2\leq k\leq n}$. An edge coloring of ${\displaystyle G}$ is called a ${\displaystyle k}$-rainbow coloring if for every set ${\displaystyle S}$ of ${\displaystyle k}$ vertices of ${\displaystyle G}$, there is a rainbow tree in ${\displaystyle G}$ containing the vertices of ${\displaystyle S}$. The ${\displaystyle k}$-rainbow index ${\displaystyle {\text{rx}}_{k}(G)}$ of ${\displaystyle G}$ is the minimum number of colors needed in a ${\displaystyle k}$-rainbow coloring of ${\displaystyle G}$. A ${\displaystyle k}$-rainbow coloring using ${\displaystyle {\text{rx}}_{k}(G)}$ colors is called a minimum ${\displaystyle k}$-rainbow coloring. Thus ${\displaystyle {\text{rx}}_{2}(G)}$ is the rainbow connection number of ${\displaystyle G}$.

Rainbow connection has also been studied in vertex-colored graphs. This concept was introduced by Krivelevich and Yuster.[5] Here, the rainbow vertex-connection number of a graph ${\displaystyle G}$, denoted by ${\displaystyle {\text{rvc}}(G)}$, is the minimum number of colors needed to color ${\displaystyle G}$ such that for each pair of vertices, there is a path connecting them whose internal vertices are assigned distinct colors.