Computer Science – Computational Complexity
Scientific paper
2011-10-14
Computer Science
Computational Complexity
13 pages
Scientific paper
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.
Huang Xiaolong
Li Xueliang
Shi Yongtang
No associations
LandOfFree
Rainbow connections for planar graphs and line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rainbow connections for planar graphs and line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow connections for planar graphs and line graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-522279