Abstract:
Graph coloring is a well known problem with wide-ranging applications. The vertex and
edge coloring problems have been studied in various models of computation. Rainbow
coloring is a type of edge coloring that also acts as a connectivity measure for graphs. It
was first introduced by Chartrand et al. in 2008.In 2011 Chakrobarty et al. proved that, it
NP-Hard to compute rainbow connection number of a graph.
In this thesis first we have define some notation for graph and rainbow coloring. Then
we do a literature overview of the results about rainbow coloring. In the final part we
have proved that, if G is a square of tree, then rc(G) 2 {diam(G),diam(G) + 1},and the
corresponding optimal rainbow coloring can be found in the time that is linear in the size
of G.