کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708865 | 1012836 | 2012 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs](/preview/png/1708865.png)
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.
Journal: Applied Mathematics Letters - Volume 25, Issue 3, March 2012, Pages 237–244