Color code techniques in rainbow connection

Abstract

Let G be a graph with an edge k-coloring γ : E(G) → {1, …, k} (not necessarily proper). A path is called a rainbow path if all of its edges have different colors. The map γ is called a rainbow coloring if any two vertices can be connected by a rainbow path. The map γ is called a strong rainbow coloring if any two vertices can be connected by a rainbow geodesic. The smallest k for which there is a rainbow k-coloring (resp. strong rainbow k-coloring) on G is called the rainbow connection number (resp. strong rainbow connection number) of G, denoted rc(G) (resp. src(G)). In this paper we generalize the notion of “color codes” that was originally used by Chartrand et al. in their study of the rc and src of complete bipartite graphs, so that it now applies to any connected graph. Using color codes, we prove a new class of lower bounds depending on the existence of sets with common neighbours. Tight examples are discussed, involving the amalgamation of complete graphs, generalized wheel graphs, and a special class of sequential join of graphs.