Rainbow Connections of Graphs: A Survey

By Xueliang Li, Yongtang Shi, Yuefang Sun. Graphs Comb., 2011

295 citations recorded by the source corpus.

The concept of rainbow connection was introduced by Chartrand et al. [14] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/cda486c2730d987a6e79615047cdca97a8945a28