Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph GG (the coloring may not be proper), a rainbow path   in GG is a path without two edges colored the same; GG is rainbow connected   if for any two vertices of GG, there is a rainbow path connecting them. Rainbow connection number  , rc(G)rc(G), of GG is the minimum number of colors needed to color its edges such that GG is rainbow connected. Chakraborty et al. (2011)  [5] proved that computing rc(G)rc(G) is NP-hard   and deciding if rc(G)=2rc(G)=2 is NP-complete  . When edges of GG are colored with fixed number kk of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether GG is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is kk rainbow connected for suitably large kk and can be given a rainbow coloring in polynomial time.