# 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.