Rainbow connections for outerplanar graphs with diameter 2 and 3

摘要

An edge-colored graph G is rainbow connected if every two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. It was proved that computing rc(G) is an NP-hard problem, as well as that even deciding whether a graph has rc(G)=2 is NP-complete. Li et al. proved that rc(G)⩽5 if G is a bridgeless graph with diameter 2, while rc(G)⩽9 if G is a bridgeless graph with diameter 3. Furthermore, Uchizawa et al. showed that determining the rainbow connection number of graphs is strongly NP-complete even for outerplanar graphs. In this paper, we give upper bounds of the rainbow connection number of outerplanar graphs with small diameters.