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 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:[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. 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.[2] Moreover, this is tight as witnessed by e.g. odd cycles. For every bridgeless graph G with radius r, rc(G)\le r(r+2).[3]

The very strong rainbow connection number (vsrc(G)) is the minimum number of colors required to color the edges of a graph G such that every shortest path between any two vertices is a rainbow path. While approximating vsrc(G) for a general graph G is an NP-hard problem, it can be solved in polynomial time for certain graph classes, such as cactus graphs.[4]

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.[5] 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

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

See also

Notes

  1. ^ Chartrand et al. (2008).
  2. ^ Ekstein et al. (2013).
  3. ^ Basavaraju, M.; Chandran, L. S.; Rajendraprasad, D.; Ramaswamy, A. (2014). "Rainbow connection number and radius". Graphs and Combinatorics. 30 (2): 275-285.
  4. ^ Chandran, L. S.; Das, A.; Issac, D. (2025). "Algorithms and Bounds for Very Strong Rainbow Coloring". Bulletin of the Malaysian Mathematical Sciences Society. 48: 96. doi:10.1007/s40840-025-01876-8
  5. ^ Chakraborty et al. (2011).
  6. ^ Chartrand, Okamoto & Zhang (2010).
  7. ^ Krivelevich & Yuster (2010).

References