Raibow coloring of a graph is an edge coloring with the property that
between any pair of vertices there is a rainbow path: i.e. a path where the colors on the edges of this path are all distinct. The minimum number of colors required to rainbow-color a graph is the rainbow connection number of the graph. I will describe some of our interesting results on this topic. I will also explain some interesting algorithmic questions regarding rainbow coloring.