# Rainbow coloring

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Rainbow_coloring
> Markdown URL: https://mediated.wiki/source/Rainbow_coloring.md
> Source: https://en.wikipedia.org/wiki/Rainbow_coloring
> Source revision: 1350110697
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [graph theory](/source/Graph_theory), a [path](/source/Path_(graph_theory)) in an [edge-colored graph](/source/Edge_coloring) 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](/source/Vertex_(graph_theory)). If there is a rainbow [shortest path](/source/Path_(graph_theory)) 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](/source/Diameter_(graph_theory)) 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](/source/Edge_(graph_theory)) 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](/source/Complete_graph).
- \text{rc}(G) = \text{src}(G) = m if and only if G is a [tree](/source/Tree_(graph_theory)).

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](/source/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](/source/Cactus_graph).[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](/source/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](/source/Wheel_graph).[1]

## Complexity

The problem of deciding whether \text{rc}(G) = 2 for a given graph G is [NP-complete](/source/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](/source/Raphael_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

- [Rainbow matching](/source/Rainbow_matching)

## Notes

1. Chartrand et al. (2008).

1. Ekstein et al. (2013).

1. Basavaraju, M.; Chandran, L. S.; Rajendraprasad, D.; Ramaswamy, A. (2014). "Rainbow connection number and radius". *Graphs and Combinatorics*. **30** (2): 275-285.

1. 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](https://doi.org/10.1007/s40840-025-01876-8)

1. Chakraborty et al. (2011).

1. Chartrand, Okamoto & Zhang (2010).

1. Krivelevich & Yuster (2010).

## References

- Chartrand, Gary; Johns, Garry L.; McKeon, Kathleen A.; Zhang, Ping (2008), "Rainbow connection in graphs", *Mathematica Bohemica*. **133** (1): 85–98, [doi:10.21136/MB.2008.133947](https://doi.org/10.21136/MB.2008.133947). [hdl:10338.dmlcz/133947](https://hdl.handle.net/10338.dmlcz/133947).
- Chartrand, Gary; Okamoto, Futaba; Zhang, Ping (2010), "Rainbow trees in graphs and generalized connectivity", *Networks*. **55** (4): NA, [doi:10.1002/net.20339](https://doi.org/10.1002/net.20339). [S2CID 7505197](https://api.semanticscholar.org/CorpusID:7505197).
- Chakraborty, Sourav; Fischer, Eldar; Matsliah, Arie; Yuster, Raphael (2011), "Hardness and algorithms for rainbow connection", *Journal of Combinatorial Optimization*. **21** (3): 330–347, [arXiv:0809.2493](https://arxiv.org/abs/0809.2493). [doi:10.1007/s10878-009-9250-9](https://doi.org/10.1007/s10878-009-9250-9). [S2CID 10874392](https://api.semanticscholar.org/CorpusID:10874392).
- 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](https://doi.org/10.1002/jgt.20418).
- Li, Xueliang; Shi, Yongtang; Sun, Yuefang (2013), "Rainbow Connections of Graphs: A Survey", *[Graphs and Combinatorics](/source/Graphs_and_Combinatorics)*. **29** (1): 1–38, [arXiv:1101.5747](https://arxiv.org/abs/1101.5747). [doi:10.1007/s00373-012-1243-2](https://doi.org/10.1007/s00373-012-1243-2). [S2CID 253898232](https://api.semanticscholar.org/CorpusID:253898232).
- 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, [arXiv:1110.5736](https://arxiv.org/abs/1110.5736). [doi:10.1016/j.disc.2012.04.022](https://doi.org/10.1016/j.disc.2012.04.022). [S2CID 16596310](https://api.semanticscholar.org/CorpusID:16596310).

---
Adapted from the Wikipedia article [Rainbow coloring](https://en.wikipedia.org/wiki/Rainbow_coloring) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Rainbow_coloring?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.