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 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 strong rainbow colored.^[1]

Definitions and bounds

The rainbow connection number of a graph $G$ is the minimum number of colors needed to rainbow color $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 strong rainbow color $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 color 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 strong rainbow colored graph is rainbow colored, we have that $\text{diam}(G) \leq \text{rc}(G) \leq \text{src}(G) \leq m$.

The following are the extremal cases:^[1]

• $\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. When $G$ is 2-connected, we have that $\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:

• $\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.^[1]

• $\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.^[1]

Complexity

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

Variants and generalizations

Krivelevich and Yuster generalized the concept of rainbow connection to the vertex version.^[4] The rainbow vertex-connection number of a graph $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, and is denoted by $\text{rvc}(G)$.

Chartrand, Okamoto and Zhang^[5] 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$.

See also

• Rainbow matching

Notes

1. Chartrand et al. (2008).
2. Ekstein et al. (Camacho).
3. Chakraborty et al. (2011).
4. Krivelevich & Yuster (2010).
5. Chartrand, Okamoto & Zhang (2010).

References

• Chartrand, Gary; Johns, Garry L.; McKeon, Kathleen A.; Zhang, Ping (2008), "Rainbow connection in graphs", Mathematica Bohemica 133 (1).
• Chartrand, Gary; Okamoto, Futaba; Zhang, Ping (2010), "Rainbow trees in graphs and generalized connectivity", Networks 55 (4).
• Chakraborty, Sourav; Fischer, Eldar; Matsliah, Arie; Yuster, Raphael (2011), "Hardness and algorithms for rainbow connection", Journal of Combinatorial Optimization 21 (3): 330–347, doi:10.1007/s10878-009-9250-9.
• Krivelevich, Michael; Yuster, Raphael (2010), "The Rainbow Connection of a Graph Is (at Most) Reciprocal to Its Minimum Degree", Journal of Graph Theory 63 (3): 185–191, doi:10.1002/jgt.20418.
• Li, Xueliang; Shi, Yongtang; Sun, Yuefang (2013), "Rainbow Connections of Graphs: A Survey", Graphs and Combinatorics 29 (1): 1–38, doi:10.1007/s00373-012-1243-2.
• Li, Xueliang; Sun, Yuefang (2012), Rainbow connections of graphs, Springer, p. 103, ISBN 978-1-4614-3119-0.
• Ekstein, Jan; Holub, Přemysl; Kaiser, Tomáš; Koch, Maria; Camacho, Stephan Matos; Ryjáček, Zdeněk; Schiermeyer, Ingo (2013), "The rainbow connection number of 2-connected graphs", Discrete Mathematics 313 (19): 1884–1892, doi:10.1016/j.disc.2012.04.022.