Rainbow connections for planar graphs and line graphs

Abstract

An edge-colored graph $G$ is rainbow connected if any 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. It is known that deciding whether a given edge-colored graph is rainbow connected is NP-Complete. We will prove that it is still NP-Complete even when the edge-colored graph is a planar bipartite graph. We also give upper bounds of the rainbow connection number of outerplanar graphs with small diameters. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It is known that deciding whether a given vertex-colored graph is rainbow vertex-connected is NP-Complete. We will prove that it is still NP-Complete even when the vertex-colored graph is a line graph.

13 pages

References in corpus (7)

• Rainbow Connection Number and Connected Dominating Sets
• New Hardness Results in Rainbow Connectivity
• Rainbow connection in $3$-connected graphs
• Note on the complexity of deciding the rainbow connectedness for bipartite graphs
• Rainbow connection of graphs with diameter 2
• Sharp upper bound for the rainbow connection number of a graph with diameter 2
• A sharp upper bound for the rainbow 2-connection number of 2-connected graphs

Cited by in corpus (1)

• Further Hardness Results on Rainbow and Strong Rainbow Connectivity