For a connected graph G, the rainbow connection number rc(G) is the minimum number of colours required to colour the edges of G so that, any two vertices are connected by a "rainbow" path (i.e., using distinct colours). The function rc(G) was introduced by Chartrand, Johns, McKeon and Zhang in 2008, and has since attracted considerable interest. In this talk, we consider generalisations and different versions of the function rc(G). For example, if G is k-connected, then we can generalise rc(G) to the rainbow k-connection number rc_k(G), which is the minimum number of colours required to colour the edges of G so that, any two vertices are connected by k internally vertex-disjoint rainbow paths. On the other hand, a different version of rc(G) considers vertex-colourings. Many results and open problems will be presented. Based on a combination of joint works with Rui Carpentier (Universidade de Cabo Verde, Republic of Cape Verde), Shinya Fujita (Maebashi Institute of Technology, Japan), Colton Magnant (Georgia Southern University, GA, USA), Ângela Mestre (CELC, Univ. Lisboa), Manuel Silva (Univ. Nova de Lisboa), and Teresa Sousa (Univ. Nova de Lisboa).
|