The Backbone Coloring Of Graphs

A graph G = (V, E) contains a finite nonempty set V of objects called vertices and a set E of 2-element subsets of V called edges. The set V and E are the vertex set and edge set of G. A graph which does not contain parallel edges or loop is called simple graph.A k-coloring of a graph G is a mapping f from the vertex set V(G) to the color set{1,2,…,k}. We say that f is proper if f(v)≠f(u) for any two adjacent vertices u and v. The chromatic number, denoted byχ(G) of G is the smallest k such that G has a proper k-coloring.Given a graph G and its subgraph H, a backbone-k-coloring of (G, H) is a k-coloring f:V(G)→{1,2,…,k} such that|f(u)-f(v)|≥2 if uv∈E(H) and|f(u)-f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G, H) is the smallest integer k such that (G,H) has a backbone-k-coloring, denoted byχb(G, H).In recent years, many known coloring problems related to frequency assignment fit into this general framework. We will discuss the following types of problems, such as Distant-2 coloring, Radio Coloring and so on. The Backbone coloring was first introduced by HajoBroersma, who had done a lot of work on it.It has proved the relationship between the upper bounds of Xb(G, H) andχ(G), where G is a graph and H is respectively a spanning tree, a spanning path,a perfect matching or some pairwise disjoint stars. It also has proved Xb(G,T), where G= T∪C is a Halin graph and T is a spanning tree of G.In this thesis, we mainly study Xb(G, H), where G is a mycielski graph, a general- ized petersen graph and a Halin Graph and so on, and H is a spanning tree, a spanning path and a perfect matching.In chapter 1, we Let G be a Graph and TG be a spanning tree of G. Let M(G) be the mycielski graph of graph G. We need to study the relationship betweenχb(G ,TG) andχb(M(G),T') with respect to given spanning tree T' of M(G). we also need to study the relationship between Xb(G, TG) andχb(M(G), T") with respect to given spanning tree T" of M(G). Then we need to characterizeχb(M(G),T"), if G is a bipartite graph, a complete graph and a Halin Graph. In chapter 2, let G be a graph and H be a subgraph of G. In this paper, we need to characterize the backbone chromatic number of generalized petersen graph, where the subgraph is the spanning tree T0 or the perfect matching M.