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

[1] The rainbow connection number of a graph

is the minimum number of colors needed to rainbow-connect

Similarly, the strong rainbow connection number of a graph

is the minimum number of colors needed to strongly rainbow-connect

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

(i.e. the length of the longest shortest path).

denotes the number of edges in

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] The above shows that in terms of the number of vertices, the upper bound

In fact, a rainbow coloring using

colors can be constructed by coloring the edges of a spanning tree of

The remaining uncolored edges are colored arbitrarily, without introducing new colors.

[2] Moreover, this is tight as witnessed by e.g. odd cycles.

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

Chartrand, Okamoto and Zhang[4] generalized the rainbow connection number as follows.

be an edge-colored nontrivial connected graph of order

is a rainbow tree if no two edges of

is the minimum number of colors needed in a

colors is called a minimum

is the rainbow connection number of

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

, is the minimum number of colors needed to color

such that for each pair of vertices, there is a path connecting them whose internal vertices are assigned distinct colors.