On The Rainbow Connections For Planar And Line Graphs

Suppose in a cellular network, people wish to transfer messages between any two vertices in a route, and require that each edge on the route between the vertices is assigned a distinct channel. In order to transfer messages between any two vertices, what is the minimum number of distinct channels that we use in network? This number is precisely the rainbow connection number, which was introduced by Chartrand et al. in2008.Let G be a nontrivial connected graph. An edge coloring of G is a function c:E(G)â†'C, where C={1,2,..., k}, is a set of k different colors. In such coloring, adjacent edges may have the same color. A path in G is called rainbow if no two edges of the path share the same color. An edge-colored graph G is rainbow connected if for every pair of distinct vertices u and v of G, there exists at least one rainbow path in G joining u and v. An edge-coloring which makes G rainbow connected is called a rainbow coloring of G. 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.A vertex-colored graph is rainbow vertex-connected if every two vertices are connected by a path whose internal vertices have distinct colors (such path is called vertex rainbow path). 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. The definition of rainbow vertex-connection was proposed by Krivelevich and Yuster.First of all, we start the research of rainbow (vertex-) connection from its algorithmic aspects. For general graphs, Chakraborty et al. proved that given an edge-colored graph G, checking whether the given coloring makes G rainbow connected is NP-complete. In fact, the investigation on special graphs could help us understand the behavior of rainbow connection better. Therefore, we consider the following decision problem for special graph classes:what is the complexity of deciding whether a given edge-coloured graph G is rainbow connected (with an unbounded number of colors)? Motivated by this challenge, we study the decision problem for planar graphs and planar bipartite graphs. We prove that given an edge-colored planar graph G, checking whether the given coloring makes G rainbow connected is NP-complete. Furthermore, we prove that given an edge-colored planar bipartite graph G, checking whether the given coloring makes G rainbow connected is NP-complete.For rainbow vertex connection, analogously, what is the complexity of decid-ing whether a given vertex-coloured graph G is rainbow vertex connected? We consider line graphs, and prove that this decision problem is NP-complete. This is a stronger result than previous related work.Secondly, we compute the upper bounds for rainbow connection number of planar graphs. Planar graphs are a very large graph class, but there are few results of rainbow connection number of planar graphs. A natural problem arise:given a planar graph G, find good upper bounds for the rainbow connection number rc(G). This thesis investigates upper bounds for rainbow connection number of bridgeless outerplanar graphs. Let G be a bridgeless outerplanar graph. If G has diameter two, then rc(G)≤3; if G has diameter three, then rc(G)≤6. Those results answer the above problem partially.This thesis consists of four chapters.In Chapter1, we provide the required background of rainbow (vertex-) con-nection, and list some terminology and notations. We also give an overview of results on rainbow (vertex-) connection including the main results of this thesis. In Chapter2, we prove that deciding if a given edge-colored planar graph is rainbow connected is NP-complete. Furthermore, we prove that it is still NP-complete even when the edge-colored graph is a planar bipartite graph.In Chapter3, we focus on the bridgeless outerplanar graphs and compute the upper bounds of rainbow connection numbers. In particular, let G be a bridgeless outerplanar graph. If diam(G)=2, then rc(G)<3, this bound is sharp; if diam(G)=3, then rc(G)≤6.In Chapter4, we show that deciding if a given vertex-colored line graph is rainbow vertex-connected is NP-complete.