Rainbow k-connection in Dense Graphs (Extended Abstract)

An edge-colouring of a graph G is rainbow k-connected if, for any two vertices of G, there are k internally vertex-disjoint paths joining them, each of which is rainbow (i.e., all edges of each path have distinct colours). The minimum number of colours for which there exists a rainbow k-connected colouring for G is the rainbow k-connection number of G, and is denoted by rc k ( G ) . The function rck(G) was introduced by Chartrand et al. in 2008, and has since attracted considerable interest. In this note, we shall consider the function rc k ( G ) for complete bipartite and multipartite graphs, highly connected graphs, and random graphs.