Since computing \(rc(G)\)  is NP-Hard [1]}, it is natural to ask for approximation algorithms for rainbow colouring a graph. Our proof for the \(r(r+2)\)  bound is constructive and hence yields a \((r+2)\) -factor approximation algorithm to rainbow colour any bridgeless graph \(G\)  of radius \(r\) . Note that \(r\)  is a lower bound on \(rc(G)\)  and hence the approximation factor. We show that this algorithm runs in \(O(nm)\)  time, where \(n\)  and \(m\)  are the number of vertices and edges of \(G\)  respectively. We also present an algorithm which has a smaller running time of \(O(dm)\)  but with a slightly poorer approximation ratio of \((d+2)\) , where \(d\)  is the diameter of \(G\) . Both these algorithms are described in Section REF . Bridges in a connected graph can be found in \(O(m)\)  time [2]}. Contracting every bridge of a general connected graph gives a bridgeless graph and its rainbow colouring can be extended to the original graph by giving a new colour to every bridge. Using these ideas, we give a \((r+3)\) -factor approximation algorithm which runs in \(O(nm)\)  time and a \((d+3)\) -factor approximation algorithm which runs in \(O(dm)\)  time to rainbow colour any connected graph \(G\)  on \(n\)  vertices, with \(m\)  edges, diameter \(d\)  and radius \(r\)  (Section REF ).
