The Backbone Coloring Of Graphs

A graph G is a pair G = (V. E), which 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 does not consist parallel edges and loop that is called simple graph.A k-coloring of a graph G is a mappingφfrom the vertex set V(G) to the color set{1,2,…, k}. We say thatφis proper ifφ(v)≠φ(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.Give a graph G and its subgraph H, a backbone-k-coloring of(G, H) is a k-coloringf: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 BB(G,H).As this years, many known colorings 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. The Backbone coloring was first introduced by HajoBroersma, who has done a lot of work on it.It has proved the relationship between the upper bounds of BB(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 BB(G,T), where G T∪C is a Halin graph and T is a spanning tree of G.In this article, we mainly study BB(G, H), where G is respectively a planar graph, and H is spanning tree.In chapter 2, we show that if G is a C4-free planar graph, then there exists a spanning tree T such that BB(G,T)≤4. And In chapter 3, we show that if G is either a C3-free or C5-free planar graph or a graph satisfied that mad(G)< 3, then there exists a spanning tree T such that BB(G, T)≤4.